← 返回题目列表

AtCoder · arc018_4

D. 我没有很多朋友

中文机器翻译题面 查看原题

問題文

高桥每年都会上大学。 N 我们欢迎新生。 N 对于新生 1 到 N 学号按顺序分配,高桥的学号是 1 。 现在,从四月开始就读大学的高桥君正在 N-1 我想和所有的新生交朋友。然而,众所周知,实现这一目标的成本非常昂贵。 对于高桥先生来说,“与x先生成为朋友”是指可以接触到x先生的状态。 目前,新同学之间根本不认识,也不是朋友。高桥自然是没有朋友的。然而,对于两名特定学生(有时也包括高桥),高桥表示:“其中至少一名学生的学生证号码表明他们是高桥的朋友或高桥本人。” 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 三个整数,代表两个学生的学号及其在仪器中的成本 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,000,000,007 后的余数输出到一行,中间用半角空格隔开。
请在输出末尾添加换行符。

入力例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 是的。
  • 2,3,4 种方法。
  • 具体来说,我将解释高桥君如何与所有学生成为朋友。
    1. 首先,高桥君没有朋友,所以高桥君(学生证号) 1) 只能使用。因此,意味着 使用 4 ,高桥君(学生证号) 1)和学号 与 4 学生交朋友。
    2. 接下来,此时学生证号 4 学生已经是高桥的朋友,所以 可以使用 3 。因此,意味着 使用 3 的学生 ID 号 3 学生及学号 4 学生交朋友。
    3. 最后,手段 2 的学生 ID 号 2 学生及学号 3 学生交朋友。
    如果您按照上述顺序使用方法,高桥将能够 6,000 只需支付日元费用,即可与所有新生交友。

    入力例2

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

    出力例2

    3000 4
    
    1 番目~ 5 第总和 手段有 5 类型。高桥与所有新生成为朋友所需的最低成本为 3,000 实现这一目标的手段组合如下: 4 是的。
  • 2,4,5 种方法。
  • 1,4,5 种方法。
  • 1,2,5 种方法。
  • 2,2,4 种方法。
  • 下图是输入示例 2 及其答案的直观表示。连接新学生的线对应于手段。
    如何选择可能的手段如下。 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