Cactusophobia

Time limit2sMemory limit512 MB

Summary

Given an edge cactus with colored edges, remove the fewest edges to make it a tree while keeping as many distinct colors as possible, then print that maximum count.

Level: Medium7 of 10
Topics: Graph, DFS
Solved: No attempts yet

Statement

A tree is a connected undirected graph with no cycles. An edge cactus is a connected undirected graph without loops or parallel edges, such that each edge belongs to at most one cycle.

Vasya has an edge cactus, and each edge has a color.

Vasya wants to remove the minimum number of edges so that the cactus becomes a tree. Among all ways to do this, he wants the resulting tree to have as many different edge colors as possible. Find the maximum number of different colors the resulting tree can have.

Input

The first line contains two integers $n$ and $m$ ( $2 \le n \le 10000$ ), the number of vertices and edges. Each of the next $m$ lines contains three integers $u$ , $v$ , and $c$ ( $1 \le u, v \le n$ , $u \ne v$ , $1 \le c \le m$ ), the endpoints of an edge and its color. The graph is guaranteed to be an edge cactus.

Output

Print one integer, the maximum number of different colors the resulting tree can have.

Examples2

Example 1
Input
```
4 4
1 2 4
2 3 1
3 4 2
4 2 3
```
Expected output
```
3
```

Example 2

Input

Expected output