비용 Batch Compilation commands

간선(혹은 에지)에 가중치가 주어진 그래프가 있다. 정점들의 수가 $N$일 때, 모든 정점은 1부터 $N$까지 번호가 붙여져 있고, 모든 간선들의 가중치는 서로 다르다. 이 때 서로 다른 두 정점 $u,v$에 대하여, $Cost(u,v)$는 다음에서 제거되는 간선들의 가중치 합이다: $u$와 $v$ 사이의 경로가 있으면 이 그래프의 최소 가중치 간선을 그래프에서 제거한다. 이 과정을 $u$와 $v$ 사이의 경로가 없을 때까지 반복한다.

예를 들어, 6개의 정점으로 이루어진 다음 그래프를 고려해 보자.

두 정점 2, 6에 대하여, $Cost(2,6)$을 구하는 과정에서 제거되는 간선들을 차례대로 나열하면 다음과 같다: $(2, 3), (4, 5), (3, 5), (3, 4), (2, 6)$. 이들 간선들 중 (2, 6)이 제거될 때, 두 정점 2와 6사이의 경로가 없으므로 간선 제거가 끝나게 된다. 따라서 $Cost(2,6) = 2 + 3 + 4 + 5 + 6 = 20$이다.

간선에 가중치가 있는 그래프가 주어질 때, $u < v$인 모든 두 정점 $u, v$에 대한 $Cost(u, v)$들의 총 합을 구하는 프로그램을 작성하시오. 총 합이 $10^{9}$보다 크면 이를 $10^{9}$으로 나눈 나머지를 출력한다.

프로그램의 실행시간은 1초를 넘을 수 없으며, 각 데이터에 대한 부분점수는 주어지지 않는다.

입력 형식

첫 번째 줄에 정점의 수 $N$과 간선의 수 $M$이 빈칸을 사이에 두고 주어진다. 다음 $M$개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 $x, y, w$ ($1 \le x, y \le N, 1 \le w \le 100,000$)가 빈칸을 사이에 두고 주어진다. 이는 간선 $(x,y)$의 가중치가 $w$임을 의미한다.

출력 형식

$u < v$인 모든 두 정점 $u, v$에 대한 $Cost(u, v)$들의 총 합을 첫째 줄에 출력한다. 단, 총 합이 $10^9$보다 크면 이를 $10^9$으로 나눈 나머지를 출력한다.

서브태스크

서브태스크 1 (4.8점)

$1 \le N, M \le 100$

서브태스크 2 (7.2점)

$1 \le N, M \le 10,000$

서브태스크 3 (12점)

$1 \le N, M \le 100,000$

입력과 출력의 예

입력

6 7
1 2 10
2 3 2
4 3 5
6 3 15
3 5 4
4 5 3
2 6 6

출력

256