Preservation of the Graph Core

Consider an undirected weighted graph \(G\) with \(n\) nodes and \(m\) edges. The nodes are numbered \(1,2,\dots,n\). For each \(i\) (\(1 \le i \le m\)), the \(i\)th edge connects nodes \(u_i\) and \(v_i\) with weight \(w_i\). It is guaranteed that \(G\) is connected and has no self-loops or multiple edges.

Over time, the graph \(G\) is degraded into a directed weighted graph \(G'\) on the same \(n\) nodes. For each edge \(i\) (\(1 \le i \le m\)), independently one of the following four outcomes happens with equal probability \(\frac{1}{4}\):

\[ \begin{array}{ll} \text{(a)} & \text{Both directed edges } u_i\to v_i \text{ and } v_i\to u_i \text{ appear, each with weight } w_i;\\[1mm] \text{(b)} & \text{Only the edge } v_i \to u_i \text{ (with weight } w_i\text{) appears; }\\[1mm] \text{(c)} & \text{Only the edge } u_i \to v_i \text{ (with weight } w_i\text{) appears; }\\[1mm] \text{(d)} & \text{No edge between } u_i \text{ and } v_i \text{ appears.} \end{array} \]

In \(G\) the core is defined as the minimum spanning tree (MST) (with total weight \(S\)). In a directed graph, a set \(E\) of \(n-1\) directed edges is called an _out‐arborescence_ if there exists a node \(x\) (called the root) such that every other node is reachable from \(x\) by traversing edges in \(E\). The core of \(G'\) is defined as the minimum out‐arborescence, i.e. an out‐arborescence with minimum total weight.

Small \(Y\) wishes that the core remains unchanged by time. In other words, he is interested in the probability that \(G'\) has an out‐arborescence (its minimum one) with total weight exactly \(S\) (the MST weight of \(G\)).

It can be shown that the answer is a rational number \(\frac{a}{b}\) in lowest terms with \(b\) not divisible by \(10^9+7\). You are required to output an integer \(x\) such that \(0 \le x < 10^9+7\) and

\[ a \equiv b\,x \pmod{10^9+7}. \]

A key observation is that if one fixes an MST \(T\) of \(G\) (which has \(n-1\) edges), then for any chosen root the required orientation on each edge is achieved with probability \(\frac{1}{2}\) (since an edge appears in the required direction if either it appears as a single directed edge in that direction or as both directions). An inclusion–exclusion analysis shows that, regardless of the structure of \(T\), the probability that there exists a root of \(T\) such that every edge is oriented appropriately is exactly \(\frac{n+1}{2^n}\).

Thus, the answer you need to output is \(x = (n+1)\cdot 2^{-n}\) modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space. Each of the following \(m\) lines contains three integers \(u, v, w\), representing an edge connecting node \(u\) and node \(v\) with weight \(w\). It is guaranteed that \(G\) is connected and there are no self-loops or multiple edges.

outputFormat

Output a single integer \(x\) (with \(0 \le x < 10^9+7\)) such that if the answer is the rational number \(\frac{a}{b}\) in lowest terms then \(a \equiv b\,x \pmod{10^9+7}\).

sample

2 1
1 2 3

750000006