Treasure Hunt: Minimum Different Ticket Costs

Alice is stranded on an island with ( n ) areas and ( m ) bidirectional paths connecting them. Each path connects two areas and has a ticket cost. Alice needs to visit every area at least once and wants to minimize the number of different ticket costs she carries. Formally, given a graph ( G=(V,E) ) with ( |V| = n ) and each edge ( e \in E ) having a cost ( c_e ), find a spanning tree ( T \subseteq E ) such that the number of distinct costs among the edges in ( T ) is minimized. Your task is to compute this minimum number of different ticket costs.

inputFormat

The first line contains two integers ( n ) and ( m ), representing the number of areas and the number of paths, respectively. Each of the following ( m ) lines contains three integers ( u ), ( v ) and ( c ), indicating that there is a bidirectional path between area ( u ) and area ( v ) with a ticket cost ( c ).

outputFormat

Output a single integer representing the minimum number of different ticket costs needed for Alice to be able to visit every area at least once.## sample

4 4
1 2 7
2 3 9
3 4 5
4 1 6

3