Farmer John は地元の大学で夜のアルゴリズム講座を受け、最小全域木を学びました。農場の設計はもっと効率的にできると気づき、配置を簡素化したいと考えています。

農場はグラフの形で、頂点は畑、辺は畑間の道を表し、各道には長さがあります。Farmer John は同じ長さの道が最大 3 本だと気づきました。FJ は道をいくつか除いて、どの畑の組にも一意な経路がある木にしたいです。さらに辺長の合計が最小の木、すなわち最小全域木にしたいと考えています。

Farmer John を手伝って、農場のグラフから作れる最小全域木の辺長合計と、異なる最小全域木の個数を求めてください。

入力

• 行 $1$：2 整数、頂点数 $N$ と辺数 $M$、$1 \le N \le 40,000; 1 \le M \le 100,000$。頂点番号は $1\ldots N$ です。
• 行 $2\ldots M+1$：3 整数 $a_{i}$、$b_{i}$、$n_{i}$、$1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$ は頂点 $a_{i}$ から $b_{i}$ の長さ $n_{i}$ の辺を表します。同じ長さ $n_{i}$ は 3 回より多く現れません。

出力

• 行 $1$：最小全域木の長さと個数（$1,000,000,007$ を法とした値）を 2 整数で出力します。

入出力例

入力 1

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

出力 1

4 3

注記

長さ $1$ の 2 辺と、長さ $2$ のどれか 1 辺を選ぶと、長さ $4$ の最小全域木になります。

問題作成：Nathan Pinsker, 2011