Spanning Tree

Time limit1sMemory limit128 MB

Summary

Count the minimum spanning trees of a connected weighted multigraph modulo 1000003, where any weight class has at most 4 edges.

Level: Hard8 of 10
Topics: Minimum spanning tree, Union-find, Combinatorics
Solved: No attempts yet

Problem

You are given a connected weighted multigraph. Write a program that finds the number of minimum spanning trees of this graph.

Because it is a multigraph, it may contain loops (edges from a vertex to itself), and there may be several edges between the same pair of vertices.

In the given graph, at most $4$ edges share the same weight.

Input

The first line contains the number of vertices $N$ and the number of edges $M$ . ( $1 \le N \le 5 \times 10^4$ , $1 \le M \le 10^5$ ) The vertices are numbered from $1$ to $N$ .

Each of the next $M$ lines contains three integers $a$ , $b$ , and $w$ , separated by spaces. ( $1 \le a, b \le N$ , $1 \le w \le 2^{30}$ ) This means there is an edge of weight $w$ connecting vertex $a$ and vertex $b$ .

Output

On the first line, print the number of minimum spanning trees modulo $1000003$ .

Examples3

Example 1
Input
```
3 5
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8
```
Expected output
```
5
```
Example 2
Input
```
2 2
1 2 4
1 2 4
```
Expected output
```
2
```
Example 3
Input
```
3 3
1 2 1
2 3 1
1 3 1
```
Expected output
```
3
```