N

N

1

N

1

N-1

A

B

C

M

N

M

M

N

1

N

1

1,000,000,007

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

N　M
A_1　B_1　C_1
A_2　B_2　C_2
:
A_M B_M C_M

• $1$ 行目には、大学に在籍する高橋君を含む新入生の数 $N (2 ≦ N ≦ 10,000)$ と、手段の数 $M (1 ≦ M ≦ 100,000)$ が与えられる。
• $2$ 行目から $M$ 行では、手段の情報が与えられる。このうち $i (1 ≦ i ≦ M)$ 行目では、$i$ 番目の手段における 2 人の学生の学籍番号とその費用を表す 3 つの整数 $A_i,B_i,C_i (1 ≦ A_i < B_i ≦ N, 1 ≦ C_i ≦ 100,000)$ が空白区切りで与えられる。$M$ 個の手段は以下の条件を満たす。
• ある学生の組を直接友達にする手段は1つ以下である。つまり、 $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$ である。
  • 任意の費用 $K$ について、 $(C_i = K であるような手段の数) ≦ 100$ が成り立つ。
  • 高橋君が新入生全員と友達になる方法は必ず存在する。

部分点

この問題には部分点が設定されている。 下記の条件を満たすテストケースのみで構成された、 $10$ 点分のセットがある。 手段に必要な費用は全て相異なる。つまり 、 $i,j (1≦i,j≦M)$ において、 $i \neq j$ なら $C_i \neq C_j$ が成立する。 上記のセットを含む全てのテストケースに正解することで、残りの $90$ 点を得られる。

• 下記の条件を満たすテストケースのみで構成された、 $10$ 点分のセットがある。
• 上記のセットを含む全てのテストケースに正解することで、残りの $90$ 点を得られる。

1,000,000,007

4 4
1 2 4000
2 3 3000
3 4 2000
1 4 1000

6000 1

10

1

4

4

6,000

1

$2,3,4$ 番目の手段を適切な順番で用いる。

1. まず最初に、高橋君には友達がいないので、高橋君(学籍番号 $1$)が含まれる手段しか用いることができない。したがって、手段 $4$ を使い、高橋君(学籍番号 $1$)と学籍番号 $4$ の学生を友達同士にする。
2. 次に、この時点で学籍番号 $4$ の学生は既に高橋君の友達であるため、手段 $3$ を用いることができる。したがって、手段 $3$ を用いて、学籍番号 $3$ の学生と学籍番号 $4$ の学生を友達同士にする。
3. 最後に、手段 $2$ を用いて、学籍番号 $2$ の学生と学籍番号 $3$ の学生を友達同士にする。

6,000

4 5
1 2 1000
1 3 1000
2 3 2000
2 4 1000
3 4 1000

3000 4

1

5

5

3,000

4

$2,4,5$ 番目の手段を適切な順番で用いる。

$1,4,5$ 番目の手段を適切な順番で用いる。

$1,2,5$ 番目の手段を適切な順番で用いる。

$2,2,4$ 番目の手段を適切な順番で用いる。

4

6 8
1 3 1
1 2 1
2 3 1
2 4 2
3 4 2
3 6 2
4 5 2
5 6 1

7 15

12 66
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
2 3 1
2 4 1
2 5 1
2 6 1
2 7 1
2 8 1
2 9 1
2 10 1
2 11 1
2 12 1
3 4 1
3 5 1
3 6 1
3 7 1
3 8 1
3 9 1
3 10 1
3 11 1
3 12 1
4 5 1
4 6 1
4 7 1
4 8 1
4 9 1
4 10 1
4 11 1
4 12 1
5 6 1
5 7 1
5 8 1
5 9 1
5 10 1
5 11 1
5 12 1
6 7 1
6 8 1
6 9 1
6 10 1
6 11 1
6 12 1
7 8 1
7 9 1
7 10 1
7 11 1
7 12 1
8 9 1
8 10 1
8 11 1
8 12 1
9 10 1
9 11 1
9 12 1
10 11 1
10 12 1
11 12 1

11 917363797