Misha travels around the country by car. There are several cities in the country connected by roads, each road may have a number of potholes.
Misha really likes to drive on roads with a lot of holes - he participates in the popular TV show "Non-persistent cars" and for each pit he visits, he is paid one coin.
He starts his journey in any of the cities of the country and then travels along the roads between cities. Isha can travel as many times as he likes on each road, but he is paid to visit any
pits only once.
Help Misha find the best route.
Input data format
the first line contains two integers n and m number of cities and roads connecting¤
cities in the country respectively (1 <= n <= 105 , 0<= m <= 105)
The next m lines contain three space-separated integers - the cities connected by the next road and the number of holes on this road, respectively. Quantity
potholes on each road non-negative number not exceeding 106
Guaranteed¤ that no road connects a city to itself and that no two roads connect identical pairs of cities.
Vertices are numbered starting from one.
Output format
Print a single number, the maximum number of coins Misha can get.
|
Enter |
Output |
4 4
1 2 1
2 3 1
1 4 1
4 3 0
|
3 |
4 2
1 3 5
2 4 4
|
5 |
Remark
All roads are two-way; having driven in any direction along the road, Misha visits all the pits on this road. Please note that there may not be a path between some pairs of cities using existing roads.