스패닝 트리

가중치가 있는 연결 멀티그래프(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$으로 나눈 나머지를 출력한다.