아니메시 왕의 태양 항해

아니메시 왕은 태양으로 항해를 떠나기로 했다. 그는 신하 한 명만 데리고 갈 생각이다. 왕이 아끼는 신하는 아르준과 프라빈 두 명이고, 둘은 왕과 동행하려고 경쟁하고 있다. 아르준은 뛰어난 궁수라서 자신의 뛰어난 실력을 보여 왕을 감동시키려 한다. 프라빈은 영리하고 왕이 무엇을 좋아하는지 정확히 안다. 바로 완벽 그래프다.

완벽 그래프는 가중치가 있는 완전 이분 그래프로, 정점이 $2N$개이고 모든 완전 매칭의 비용이 같은 그래프다. 완전 매칭의 비용은 매칭에 포함된 $N$개 간선 비용의 합이다.

프라빈은 완벽의 숲에서 그런 그래프를 하나 찾아 상자에 보관해 두었다. 왼쪽 열의 $N$개 정점에는 $1, 2, \ldots, N$의 번호가, 오른쪽 열의 $N$개 정점에는 $N+1, N+2, \ldots, 2N$의 번호가 붙어 있다. 왼쪽 정점 $u$와 오른쪽 정점 $v$를 잇는 간선의 비용은 $C_{uv}$이다.

아르준이 상자에 구멍을 내서 간선 일부가 빠져 버렸다. 프라빈은 빠진 간선에 비용을 적절히 부여하면 그래프가 다시 완벽 그래프가 된다고 주장한다. 남은 간선만으로 빠진 간선의 비용이 하나로 정해진다. 프라빈은 이 사실을 왕에게 말하지 않았고, 왕은 모든 $N^2$개 간선 비용의 제곱합을 $10^9+7$로 나눈 나머지를 보고하라고 한다. 상자에 남은 간선의 비용이 주어지니 요구한 값을 구하라.

첫 줄에 정수 $N$과 $E$가 주어진다. 이어지는 $E$개의 줄에는 정수 $u$, $v$, $x$가 하나씩 주어진다. 이는 왼쪽 정점 $u$와 오른쪽 정점 $v$를 잇는 간선이 남아 있고, 그 비용이 $C_{uv}=x$라는 뜻이다.

빠진 간선에 비용을 부여해 주어진 그래프를 완벽 그래프로 만드는 방법은 유일하게 존재함이 보장된다.

테스트 케이스마다 답을 정수 하나로 출력하고, 한 줄에 하나씩 쓴다.

• $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$. 이 제약은 빠진 간선에는 적용되지 않으며, 빠진 간선의 비용은 이 조건을 만족할 필요가 없다.

완전 이분 그래프는 왼쪽 열의 모든 정점과 오른쪽 열의 모든 정점 사이에 간선이 있는 그래프다.

이 그래프의 완전 매칭은 어떤 두 간선도 끝점을 공유하지 않는 $N$개 간선의 집합이다.