アカベコ国の国王には２人の王子がいます。国王は自分が退位するときに国を２つに分割し、それぞれの王子に一つずつ国を治めさせることにしました。新しい国の名前はアカ国とベコ国です。アカベコ国には N 個の町と、２つの町を繋ぐ M 本の道があります。国王は、以下の手順でアカベコ国の町と一部の道を２つの国に配分することにしました。
(1) 町を２つ選び、それぞれアカ国とベコ国に配分する。
(2) すでに配分された町sを選ぶ。さらに、町 s から１本の道で繋がっている、まだ配分されていない町 t を選ぶ。そして、町 s、t 間の道と町 t を、町 s が配分された国に配分する。
(3) (2)を、行えなくなるまで繰り返す。
実は２人の王子はあまり仲が良くないので、国王は２つの国の距離をなるべく大きくしたいと考えています。ここで、２つの国の距離とは、アカ国の町とベコ国の町を繋ぐ道の中で、最も短い道の長さです。
アカベコ国の町と道の情報が与えられたとき、分配後のアカ国とベコ国の距離の最大値と、そのような距離になる配分が何通りあるかを求めるプログラムを作成してください。ただし、２つの配分結果は、アカ国とベコ国に異なる町か道が配分された場合に区別されます。
入力は以下の形式で与えられる。
N M s1 t1 d1 s2 t2 d2 : sM tM dM
１行目は２つの整数からなる。N (2 ≤ N ≤ 100) は町の数、M (N-1 ≤ M ≤ N(N-1)/2) は道の数を表す。続くM 行に２つの町を繋ぐ道が与えられる。si と ti (1 ≤ si ≠ ti ≤ N) は i 番目の道が繋ぐ２つの町の番号を表す。di (1 ≤ di ≤ 109) は i 番目の道の長さを表す。
入力は以下の条件を満たす。
分配後のアカ国とベコ国の距離の最大値と組み合わせの数を、空白区切りで１行に出力する。ただし、分配後の組み合わせの数は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。
6 7 1 2 1 2 3 2 3 1 3 4 5 4 5 6 5 6 4 6 1 4 7
7 18