스패닝 트리

시간 제한1초메모리 제한128 MB

요약

같은 가중치를 가진 간선이 최대 4개인 연결 가중치 다중 그래프에서 최소 신장 트리의 개수를 1000003으로 나눈 나머지로 구한다.

난이도: 어려움10점 중 8점
유형: 최소 신장 트리, 유니온 파인드, 조합론
정답자: 아직 제출이 없습니다

문제

가중치가 있는 연결 멀티그래프(connected weighted multigraph)가 주어진다. 이 그래프의 최소 스패닝 트리(minimum spanning tree)의 개수를 구하는 프로그램을 작성하여라.

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

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

입력

첫째 줄에 정점의 수 $N$ 과 간선의 수 $M$ 이 주어진다. ( $1 \le N \le 5 \times 10^4$ , $1 \le M \le 10^5$ ) 정점은 $1$ 번부터 $N$ 번까지 번호가 매겨져 있다.

다음 $M$ 개의 줄에는 각 간선을 나타내는 세 정수 $a$ , $b$ , $w$ 가 공백으로 구분되어 주어진다. ( $1 \le a, b \le N$ , $1 \le w \le 2^{30}$ ) 이는 정점 $a$ 와 정점 $b$ 를 잇는 가중치 $w$ 인 간선이 있음을 뜻한다.

출력

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

예제3

예제 1
입력
```
3 5
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8
```
예상 출력
```
5
```
예제 2
입력
```
2 2
1 2 4
1 2 4
```
예상 출력
```
2
```
예제 3
입력
```
3 3
1 2 1
2 3 1
1 3 1
```
예상 출력
```
3
```