비용

간선에 서로 다른 양의 가중치가 붙은 무방향 그래프가 있다. 정점은 1부터 N까지 번호가 붙어 있다.

서로 다른 두 정점 u, v에 대해 Cost(u, v)를 다음 과정에서 제거되는 간선 가중치의 합으로 정의한다.

1. 현재 그래프에서 u와 v 사이에 경로가 있으면, 현재 그래프에 남아 있는 간선 중 가중치가 가장 작은 간선을 제거한다.
2. u와 v 사이에 경로가 없어질 때까지 1번 과정을 반복한다.

다음은 정점이 6개인 그래프의 한 모습이다.

정점 2와 6에 대해 위 과정을 수행하면 간선 (2, 3), (4, 5), (3, 5), (3, 4), (2, 6)이 차례로 제거된다. 간선 (2, 6)이 제거된 뒤에는 두 정점 사이의 경로가 없어지므로 과정이 끝난다. 따라서 Cost(2, 6) = 2 + 3 + 4 + 5 + 6 = 20이다.

그래프가 주어졌을 때, u < v인 모든 정점 쌍 (u, v)에 대한 Cost(u, v)의 총합을 구하시오. 총합이 10^9 이상이면 10^9로 나눈 나머지를 출력한다.

첫째 줄에 정점의 수 N (1 < N <= 100,000)과 간선의 수 M (1 <= M <= 100,000)이 공백으로 구분되어 주어진다.

다음 M개의 줄에는 간선 하나를 나타내는 세 양의 정수 x, y, w가 공백으로 구분되어 주어진다. 이는 정점 x와 y를 잇는 간선의 가중치가 w라는 뜻이다. 모든 간선의 가중치는 서로 다르며, 1 <= w <= 100,000이다.

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