There is No Alternative

Time limit3sMemory limit256 MB

Summary

Count the bridges that appear in every minimum-cost set connecting all islands and report their total cost.

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

Problem

ICPC (Isles of Coral Park City) is made up of several islands. The residents asked the city to build bridges between the islands so that they no longer depend on boats, and they require that every island be reachable from every other island over one or more bridges.

The mayor picked a number of island pairs and had a construction company estimate the cost of a bridge for each pair. He now has to decide which bridges to build so that all the islands are connected and the total construction cost is as small as possible.

Several different sets of bridges can reach that same minimum total cost. The mayor decided to start by building only the bridges that appear in every minimum cost set. Such a bridge is called a no alternative bridge.

Given the candidate bridges and their costs, write a program that reports how many no alternative bridges there are and what their construction costs add up to.

Input

The input consists of a single test case.

N M
S1 D1 C1
.
.
.
SM DM CM

The first line contains the number of islands $N$ and the number of island pairs $M$ that a bridge may be built between. Each island is identified by an integer from $1$ to $N$ .

Each of the next $M$ lines contains three integers $S_i$ , $D_i$ and $C_i$ ( $1 \le i \le M$ ), meaning that building the bridge between island $S_i$ and island $D_i$ costs $C_i$ .

$3 \le N \le 500$ , $N - 1 \le M \le \min(50000, N(N-1)/2)$ , $1 \le S_i < D_i \le N$ , and $1 \le C_i \le 10000$ . No two bridges connect the same pair of islands, that is, if $i \ne j$ and $S_i = S_j$ , then $D_i \ne D_j$ . If all the candidate bridges are built, every island is reachable from every other island over one or more bridges.

Output

Print the number of no alternative bridges and the sum of their construction costs on one line, separated by a space.

Examples4

Example 1
Input
```
4 4
1 2 3
1 3 3
2 3 3
2 4 3
```
Expected output
```
1 3
```
Example 2
Input
```
4 4
1 2 3
1 3 5
2 3 3
2 4 3
```
Expected output
```
3 9
```
Example 3
Input
```
4 4
1 2 3
1 3 1
2 3 3
2 4 3
```
Expected output
```
2 4
```
Example 4
Input
```
3 3
1 2 1
2 3 1
1 3 1
```
Expected output
```
0 0
```