Maximum Mean Cycle

You are given a directed graph with weighted edges. Find a cycle whose average edge weight is as large as possible. The average edge weight of a cycle is defined as (the sum of the weights of its edges) divided by (the number of its edges).

The first line contains two integers $n$ and $m$ ($2 \le n \le 100$, $2 \le m \le 10^4$), the number of vertices and the number of edges. Each of the next $m$ lines contains three integers $a$, $b$, $c$ ($1 \le a, b \le n$, $a \ne b$, $0 \le c \le 10^6$), describing a directed edge from vertex $a$ to vertex $b$ with weight $c$. Between any pair of vertices there is at most one edge in each direction.

Print the maximum average edge weight over all cycles as a reduced fraction $p/q$ in lowest terms ($\gcd(p, q) = 1$, $q \ge 1$). If the value is an integer $v$, print it as $v/1$. It is guaranteed that the graph always contains at least one cycle.