시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 64 11 11 23.404%

문제

가중치가 있고, 연결되어있는 멀티 그래프 (connected weighted multigraph)가 주어졌을 때, 최소 스패닝 트리의 수를 구하는 프로그램을 작성하시오.

멀티 그래프는 루프(자기 자신으로 향하는 간선)이 있을 수 있고, 두 정점 사이에 간선이 여러 개 있을 수도 있다.

입력으로 주어지는 그래프에서 가중치가 같은 간선은 최대 4번 등장한다.

입력

첫째 줄에 정점의 수 N과 간선의 수 M이 주어진다. (1 ≤ N ≤ 5×104, 1 ≤ M ≤ 105) 정점은 1번부터 N번까지 번호가 매겨져 있다. 다음 M개 줄에는 세 정수 a, b, w가 주어지며, 공백으로 구분되어져 있다. (1 ≤ a, b ≤ N, 1 ≤ w ≤ 230) 이 뜻은 a와 b를 연결하는 간선의 가중치가 w라는 뜻이다.

출력

첫째 줄에 최소 스패닝 트리의 개수를 1000003로 나눈 나머지를 출력한다.

예제 입력

3 5
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8

예제 출력

5

힌트