최소 사이클 평균

대사 네트워크는 방향 그래프로 모형화한다. 정점은 상태를 나타내고, 간선은 한 상태에서 다른 상태로 넘어가는 전이를 나타낸다. 각 간선에는 그 전이에 드는 비용이나 에너지 같은 가중치가 붙어 있다. 방향 사이클의 평균 가중치는 사이클에 속한 간선의 가중치 합을 간선 개수로 나눈 값이다. 네트워크의 효율은 네트워크 안에 있는 방향 사이클의 평균 가중치 중 최솟값으로 측정한다. 이 최솟값을 구하면 된다.

정확히 말하면 정점이 $n$개인 방향 그래프 $G = (V, E)$가 주어지고, 모든 간선의 가중치는 양수다. 사이클 $C$ 위의 정점이 모두 서로 다르면 $C$를 단순 사이클이라고 한다. 단순 방향 사이클 $C$의 가중치 $w(C)$는 $C$에 속한 간선의 가중치 합이고, $C$의 평균 가중치는 $w(C)/|C|$이다. 여기서 $|C|$는 $C$의 간선 개수, 곧 $C$의 길이다. $G$의 최소 사이클 평균은 $G$에 있는 단순 방향 사이클의 평균 가중치 중 최솟값이다. $G$는 단순 그래프다. 한 정점에서 자기 자신으로 가는 간선이 없고, 서로 다른 두 정점 $u$, $v$에 대해 $u$에서 $v$로 가는 간선은 많아야 하나다. 따라서 $G$에 있는 모든 단순 사이클의 길이는 2 이상이다.

그림 1. 정점이 6개, 간선이 9개인 방향 그래프. 정점 a부터 f까지가 번호 0부터 5까지에 대응한다.

그림 1의 방향 그래프에는 단순 방향 사이클이 모두 네 개 있다. b에서 c로, 다시 b로 돌아오는 사이클, a에서 b, c를 거쳐 a로 돌아오는 사이클, b에서 d, e, c를 거쳐 b로 돌아오는 사이클, a에서 b, d, e, c를 거쳐 a로 돌아오는 사이클이고, 길이는 각각 2, 3, 4, 5다. 네 사이클의 가중치는 4, 6, 6, 8이므로 평균 가중치는 $4/2 = 2$, $6/3 = 2$, $6/4 = 1.5$, $8/5 = 1.6$이다. 평균이 가장 작은 사이클은 b에서 d, e, c를 거쳐 b로 돌아오는 사이클이고, 그 평균은 $1.5$다.

단순 방향 그래프 $G$의 최소 사이클 평균을 출력하는 프로그램을 작성하라.

첫 줄에 방향 그래프 $G$의 정점 개수 $n$과 간선 개수 $m$이 주어진다($2 \le n \le 1{,}000$, $1 \le m \le 10^5$). 정점의 번호는 $0$부터 $n - 1$까지 서로 다르다.

다음 $m$개 줄에는 간선이 한 줄에 하나씩 주어진다. 각 줄에는 세 정수 $u$, $v$, $w$가 공백 하나로 구분되어 주어지고, 이는 $u$에서 $v$로 가는 가중치 $w$인 간선을 뜻한다($0 \le u, v \le n - 1$, $u \ne v$, $1 \le w \le 1{,}000$).

한 줄에 두 정수 $a$와 $b$를 공백 하나로 구분해 출력한다. $a$와 $b$는 서로소이고, $a/b$가 $G$의 최소 사이클 평균이다. 최소 사이클 평균이 정수이면 $b$는 $1$이다. $G$에 사이클이 없으면 0 두 개를 공백 하나로 구분해 출력한다.