题目背景

你真的以为我们能打进全国联赛吗？

题目描述

北宇治的吹奏部一共有 $n$ 个学生，学生的编号为 $1$ 到 $n$。在泷昇到来之前已经建立了 $m$ 对配合关系（$0 \le m \le n - 1$），每对配合关系 $u,v,w$ 表示在 $u$ 或 $v$ 演奏后另一人能在 $w$ 单位的时间后立刻演奏完成配合。若两人没有直接的配合关系，也可以通过多次的配合关系来间接完成配合，他们造成的误差时间是中间每次配合花费的时间之和。

现在的吹奏部简直乱的像一盘散沙！为此，泷昇有 $n-m-1$ 种特训方案。第 $i$ 种方案可以让任意两个成员建立配合关系，最终训练的效果能让二人在 $a_i$ 的时间内完成配合。定义不协调度为对于所有的 $1\le x<y\le n$，$x,y$ 之间误差时间的最小值的和。如果有两个成员在最后无法配合，则认为不合法。为了打进全国联赛，他希望不协调度尽量的小。

请告诉泷昇这个最优的不协调度。数据保证一定存在至少一种合法的方案。因为结果可能很大，你只需要输出不协调度对 $10^9+7$ 取模的值。

输入格式

第一行，两个整数 $n, m$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一对配合关系。

若 $n-m-1>0$，则最后一行 $n-m-1$ 个整数 $a_1, \ldots, a_{n - m - 1}$。

输出格式

仅一行，一个整数，表示最小的不协调度对 $10^9+7$ 取模的值。

样例

7 3
1 2 1
3 5 3
3 7 2
1 2 3

76

样例 1 解释

之前的配合关系形如：

最优秀的训练方式训练之后的配合关系形如：

这样的话，$(1,7)$ 的误差时间的最小值是 $4$，方案是通过 $(1,2)$、$(2,3)$、$(3,7)$ 依次进行配合。

类似的，所有误差时间之和是 $76$。

可以证明不存在更优秀的合法方案。

14 9
8 9 539682
14 4 470495
10 7 265900
14 5 234094
1 9 255217
7 1 559336
7 6 883781
7 13 679978
11 1 598746
433139 142690 902471 766101

108274449

数据范围

本题采用捆绑测试。

• 子任务 1（13 分）：$n\le 6$。
• 子任务 2（22 分）：$n\le 2000$。
• 子任务 3（18 分）：在建立新的配合关系前，任意两个可以配合的成员都可以通过不超过一个中间的成员间接配合。
• 子任务 4（19 分）：$a_i=0,w=1$。
• 子任务 5（15 分）：$a_i$ 全部相同。
• 子任务 6（13 分）：无特殊性质。

对于全部的数据，$0\le m<n\le 10^6$，$0\le a_i,w\le 10^6$，$1\le u,v\le n$。