問題文
入力
输入是按以下格式从标准输入给出的。
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 三个整数,代表两个学生的学号及其在仪器中的成本 A_i,B_i,C_i (1 ≦ A_i < B_i ≦ N, 1 ≦ C_i ≦ 100,000) 用空格分隔。M 表示满足以下条件。
- 直接交一群学生朋友的方法只有一种。换句话说, 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 点积分。
出力
请在输出末尾添加换行符。
入力例1
4 4 1 2 4000 2 3 3000 3 4 2000 1 4 1000
出力例1
6000 1该输入是部分点( 10 点)满意。 1 番目~ 4 第总和 手段有 4 类型。高桥与所有新生成为朋友所需的最低成本为 6,000 实现这一目标的手段组合如下: 1 是的。
- 首先,高桥君没有朋友,所以高桥君(学生证号) 1) 只能使用。因此,意味着 使用 4 ,高桥君(学生证号) 1)和学号 与 4 学生交朋友。
- 接下来,此时学生证号 4 学生已经是高桥的朋友,所以 可以使用 3 。因此,意味着 使用 3 的学生 ID 号 3 学生及学号 4 学生交朋友。
- 最后,手段 2 的学生 ID 号 2 学生及学号 3 学生交朋友。
入力例2
4 5 1 2 1000 1 3 1000 2 3 2000 2 4 1000 3 4 1000
出力例2
3000 41 番目~ 5 第总和 手段有 5 类型。高桥与所有新生成为朋友所需的最低成本为 3,000 实现这一目标的手段组合如下: 4 是的。
入力例3
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
出力例3
7 15
入力例4
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
出力例4
11 917363797