King Animesh decides to have a voyage to the sun

King Animesh has decided to go on a voyage to the Sun and will take only one of his courtiers with him. His two favorite courtiers, Arjun and Praveen, are competing for the trip. Arjun is a great archer and plans to impress the king by showing his skill. Praveen is smart and knows exactly what the King likes: Graphs of Perfection.

A Graph of Perfection is a weighted complete bipartite graph with $2N$ vertices in which every perfect matching has the same cost. The cost of a perfect matching is the sum of the costs of its $N$ edges.

Praveen found one such graph in the Forest of Perfection and kept it in a box. The $N$ vertices in the left column are labeled $1, 2, \ldots, N$, and the $N$ vertices in the right column are labeled $N+1, N+2, \ldots, 2N$. The cost of the edge between left vertex $u$ and right vertex $v$ is $C_{uv}$.

Arjun made a hole in the box, and some edges fell out. Praveen claims he can assign costs to the missing edges so that the graph is a Graph of Perfection again. The remaining edges determine the assignment uniquely. He does not tell the King this. The King asks him to report the sum of the squares of all $N^2$ edge costs modulo $10^9+7$. You are given the costs of the edges still in the box. Find the required sum.

The first line contains two integers $N$ and $E$. Each of the next $E$ lines contains three integers $u$, $v$, and $x$. This means the edge from left vertex $u$ to right vertex $v$ is still present, and its cost is $C_{uv}=x$.

It is guaranteed that exactly one way to assign costs to the missing edges makes the given graph a Graph of Perfection.

For each test case, output a single integer on one line: the answer.

• $1 \le N \le 10^5$
• $1 \le E \le 10^6$
• $1 \le u \le N$
• $N+1 \le v \le 2N$
• $1 \le x \le 10^5$. This constraint does not apply to the missing edges, whose costs need not satisfy it.

A complete bipartite graph has an edge between every node in the left column and every node in the right column.

A perfect matching in this graph is a set of $N$ edges such that no two edges share an endpoint.