최대 평균 사이클

가중치가 있는 방향 그래프가 주어진다. 이 그래프에서 간선 가중치의 평균이 가장 큰 사이클을 찾아라. 사이클의 평균 가중치는 (사이클에 속한 간선들의 가중치 합)을 (간선의 개수)로 나눈 값으로 정의한다.

첫째 줄에 그래프의 정점 수와 간선 수를 나타내는 두 정수 $n$, $m$ ($2 \le n \le 100$, $2 \le m \le 10^4$)이 주어진다. 이어지는 $m$개의 줄에는 각 간선을 나타내는 세 정수 $a$, $b$, $c$ ($1 \le a, b \le n$, $a \ne b$, $0 \le c \le 10^6$)가 주어진다. 이는 정점 $a$에서 정점 $b$로 향하는 가중치 $c$인 간선이 존재함을 뜻한다. 임의의 두 정점 사이에는 각 방향으로 최대 한 개의 간선만 존재한다.

모든 사이클 중 간선 가중치의 평균이 최대가 되는 값을 기약분수 $p/q$ 형태로 출력한다 ($\gcd(p, q) = 1$, $q \ge 1$). 값이 정수 $v$이면 $v/1$로 출력한다. 그래프에는 항상 사이클이 하나 이상 존재함이 보장된다.