Minimizing Dissonance in the Wind Ensemble

Consider a wind ensemble with $n$ students numbered from $1$ to $n$. Before Takishō arrives, there are already $m$ established cooperation relations. Each relation is given by three integers $u$, $v$, and $w$, meaning that when either student $u$ or student $v$ plays, the other can follow and finish his part exactly $w$ time units later. If two students do not have a direct relation, they may still cooperate indirectly through a sequence of relations; the total error time between them is defined as the sum of the waiting times along the chain.

Now the ensemble is in utter disarray! To solve this, Takishō has $n - m - 1$ special training schemes available. The $i$-th scheme lets any two members establish a new cooperation relation and guarantees that after training the two can cooperate in $a_i$ time units. Once all training schemes are applied, the overall coordination error (or dissonance) is defined as the sum over all pairs $1 \le x < y \le n$ of the minimum error time between $x$ and $y$. (If some pair of students cannot cooperate in the final network, the training plan is considered invalid.) To qualify for the national league, Takishō wants to choose the training schemes so that the dissonance is minimized. Compute the optimal dissonance modulo $10^9+7$.

More formally, suppose the $m$ fixed relations form a forest (each relation is represented by an edge with weight $w$) and let the training schemes, with values $a_1,a_2,\dots,a_{n-m-1}$, be used to add edges among the components. In the final spanning tree (with $n-1$ edges) the dissonance is [ \sum_{\text{edge } e}; (\text{edge weight})\times (\text{# of pairs separated by } e), \quad\text{where the number of separated pairs by edge } e \text{ is } x\times (n-x) \text{ if one side of } e \text{ has } x \text{ nodes}. ]

The fixed edges are predetermined. You are allowed to choose any $n-m-1$ training edges among different components; furthermore, you can assign the training schemes arbitrarily to these edges. It can be shown that an optimal strategy always exists.

Your task is to output the minimum possible dissonance modulo $10^9+7$.

inputFormat

The first line contains two integers $n$ and $m$ ($1\le n\le 10^5$, $0\le m\le n-1$).

Then follow $m$ lines. Each of these lines contains three integers $u$, $v$, and $w$ ($1\le u,v\le n$, $1\le w\le 10^9$), representing an existing cooperation relation between students $u$ and $v$ with error time $w$. It is guaranteed that these $m$ relations form a forest (i.e. there are no cycles).

The next line contains $n-m-1$ integers $a_1,a_2,\dots,a_{n-m-1}$ ($1\le a_i\le 10^9$), representing the time required for cooperation if a training scheme is used.

outputFormat

Output a single integer: the minimum possible dissonance modulo $10^9+7$.

sample

4 2
1 2 1
3 4 2
3

15