Note

予備知識

品質管理の手法として良く知られたものに「新ＱＣ７つ道具」と呼ばれるものがあります．
今回はその中の一つであるところの「アローダイアグラム法」にクローズアップしてみたいと思います．
「アローダイアグラム法」はプロジェクトを達成するために必要な作業の工数や順序関係を，
下図のように図形化することでボトルネックを調べたり効率よく進捗管理するために用いられる手法のことです．


プロジェクト全体のつながりを上図のように「結合点」と「作業」でつなぎ，各作業にはその作業に必要な時間を併記します．
結合点は，プロジェクト内における各取り組みや，マイルストーンとなる区切りなどを表します．
ある結合点から作業を開始するためには，その結合点に至るすべての作業が完了している必要があります．
例えば，ある取り組みと別の取り組みの完了時期を同期させたい場合などは，作業時間$0$の矢印を書きます．
（図中の結合点$4$から結合点$5$のように）
時刻$0$からこのプロジェクトが開始するとして，完了までに必要な時間は，例えば下図のように求めることができます．



各結合点ごとに最速でいつ着手できるか（最早結合点時刻）を求めることで，全体に必要な時間を計算でき，
また各結合点ごとに最悪でいつ着手しなければ全体に遅延を生じてしまうか（最遅結合点時刻）を求めることもできます．
最遅結合点時刻と最早結合点時刻が一致するということは，着手できるようになってすぐに着手しなければならないということなので，
その結合点が全体を律速していることを意味します．
そのような結合点を結ぶことで全体のボトルネックとなる工程（クリティカルパス）を明らかにすることができます．

問題文

入力

$N$ $M$
$A_0$ $B_0$ $C_0$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_{M-1}$ $B_{M-1}$ $C_{M-1}$

入力は全て整数であり，それぞれは以下の制約を満たす．
$3\le N \le 10^5$
$2\le M \le 5 \times 10^5$
$0 \le A_i < N$ , $0 \le i < (M-1)$
$0 \le B_i < N$ , $0 \le i < (M-1)$
$0 \le C_i < 160$ , $0 \le i < (M-1)$
全体の連結性および，$0$がプロジェクト開始，$N-1$が完了であることは保証される．
また，作業のループは発生しない．

出力

$T$ $P/N$

ここで，$T$はプロジェクト全体の完了に必要な最短時間．
$P$は最短時間での完了を実現するうえで，余裕有りと見込めるのべ人員（クリティカルパス上に居ないのべ人員）の数．
$N$は与えられる$N$をそのまま出力．
最後に改行してください。

サンプル

8 12
0 1 3
1 2 7
1 3 2
2 4 1
3 4 6
2 6 4
3 5 1
4 6 2
4 5 0
4 7 4
6 7 2
5 7 4

16 3/8

5 4
0 3 3
3 1 2
1 2 3
2 4 1

9 0/5

8 12
0 1 3
0 2 3
1 3 3
1 4 3
2 3 3
2 4 3
3 5 3
3 6 3
4 5 3
4 6 3
5 7 3
6 7 3

12 0/8