Minimum Cycle Mean

A metabolic network is modeled as a directed graph. A vertex is a state, and an edge is a transition from one state to another. Each edge carries a weight, such as the cost or the energy that the transition needs. The mean weight of a directed cycle is the total weight of its edges divided by the number of its edges. The efficiency of the network is measured by the smallest mean weight among the directed cycles in the network, and your task is to compute that value.

More precisely, you are given a digraph $G = (V, E)$ with $n$ vertices in which every edge has a positive weight. A cycle $C$ in $G$ is simple if the vertices along $C$ are all distinct. The weight $w(C)$ of a simple directed cycle $C$ is the total weight of the edges in $C$, and the mean weight of $C$ is $w(C)/|C|$, where $|C|$ is the number of edges of $C$, that is, the length of $C$. The minimum cycle mean of $G$ is the smallest mean weight among the simple directed cycles of $G$. The digraph $G$ is simple: no edge goes from a vertex to itself, and for any two distinct vertices $u$ and $v$ there is at most one edge from $u$ to $v$. Every simple cycle in $G$ therefore has length at least two.

Figure 1. A digraph with 6 vertices and 9 edges. The vertices a to f correspond to the id numbers 0 to 5.

The digraph in Figure 1 has four simple directed cycles in total: b to c to b, a to b to c to a, b to d to e to c to b, and a to b to d to e to c to a, of length 2, 3, 4, and 5. Their weights are 4, 6, 6, and 8, so their mean weights are $4/2 = 2$, $6/3 = 2$, $6/4 = 1.5$, and $8/5 = 1.6$. The smallest mean weight is $1.5$, reached by the cycle b to d to e to c to b.

Write a program that prints the minimum cycle mean of a simple digraph $G$.

The first line contains two integers $n$ and $m$ ($2 \le n \le 1{,}000$, $1 \le m \le 10^5$), the number of vertices and the number of edges of the digraph $G$. The vertices have distinct id numbers from $0$ to $n - 1$.

Each of the next $m$ lines describes one edge with three integers $u$, $v$, $w$ separated by a single space. The edge is directed from $u$ to $v$ ($0 \le u, v \le n - 1$, $u \ne v$) and has weight $w$ ($1 \le w \le 1{,}000$).

Print one line with two integers $a$ and $b$ separated by a single space, where $a$ and $b$ are relatively prime and $a/b$ is the minimum cycle mean of $G$. When the minimum cycle mean is an integer, $b$ is $1$. If $G$ has no cycle, print two zeroes separated by a single space.