The Kingdom of Akabeko

Time Limit : 1 sec, Memory Limit : 65536 KB

アカベコ国王の配慮

アカベコ国の国王には2人の王子がいます。国王は自分が退位するときに国を2つに分割し、それぞれの王子に一つずつ国を治めさせることにしました。新しい国の名前はアカ国とベコ国です。アカベコ国には N 個の町と、2つの町を繋ぐ M 本の道があります。国王は、以下の手順でアカベコ国の町と一部の道を2つの国に配分することにしました。

(1)   町を2つ選び、それぞれアカ国とベコ国に配分する。
(2)   すでに配分された町sを選ぶ。さらに、町 s から1本の道で繋がっている、まだ配分されていない町 t を選ぶ。そして、町 st 間の道と町 t を、町 s が配分された国に配分する。
(3)   (2)を、行えなくなるまで繰り返す。

実は2人の王子はあまり仲が良くないので、国王は2つの国の距離をなるべく大きくしたいと考えています。ここで、2つの国の距離とは、アカ国の町とベコ国の町を繋ぐ道の中で、最も短い道の長さです。

アカベコ国の町と道の情報が与えられたとき、分配後のアカ国とベコ国の距離の最大値と、そのような距離になる配分が何通りあるかを求めるプログラムを作成してください。ただし、2つの配分結果は、アカ国とベコ国に異なる町か道が配分された場合に区別されます。

入力

入力は以下の形式で与えられる。

N M
s1 t1 d1
s2 t2 d2
:
sM tM dM

1行目は2つの整数からなる。N (2 ≤ N ≤ 100) は町の数、M (N-1 ≤ MN(N-1)/2) は道の数を表す。続くM 行に2つの町を繋ぐ道が与えられる。siti (1 ≤ sitiN) は i 番目の道が繋ぐ2つの町の番号を表す。di (1 ≤ di ≤ 109) は i 番目の道の長さを表す。

入力は以下の条件を満たす。

  • どの2つの町もいくつかの道を使い行き来が可能である。
  • どの2つの町の間にも2本以上の道はない。
  • 同じ長さの道は5本以下である。

出力

分配後のアカ国とベコ国の距離の最大値と組み合わせの数を、空白区切りで1行に出力する。ただし、分配後の組み合わせの数は非常に大きくなりうるので、代わりに 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

Source: PC Koshien 2014 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-11-8
http://web-ext.u-aizu.ac.jp/pc-concours/