카투소포비아

트리는 사이클이 없는 연결된 무방향 그래프이다. 엣지 선인장은 자기 루프와 중복 간선이 없는 연결된 무방향 그래프이며, 각 간선은 많아야 하나의 사이클에 속한다.

바샤는 엣지 선인장을 가지고 있고, 각 간선에는 색이 칠해져 있다.

바샤는 선인장이 트리가 되도록 간선을 최소 개수만 제거하려 한다. 이때 남은 트리에 서로 다른 색의 간선이 가능한 한 많이 남도록 하려 한다. 결과 트리가 가질 수 있는 서로 다른 색의 최대 개수를 구하라.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($2 \le n \le 10000$). 이어지는 $m$개의 줄에는 각각 정수 $u$, $v$, $c$가 주어진다 ($1 \le u, v \le n$, $u \ne v$, $1 \le c \le m$). $u$와 $v$는 간선의 양 끝 정점이고, $c$는 간선의 색이다. 주어지는 그래프는 엣지 선인장임이 보장된다.

결과 트리가 가질 수 있는 서로 다른 색의 최대 개수를 한 줄에 출력한다.