SP11540 TRAIN07 - Training

Mirko and Slavko are training hard for the annual tandem cycling marathon taking place in Croatia. They need to choose a route to train on. There are N cities and M roads in their country. Every road connects two cities and can be traversed in both

The first line of input contains two integers N and M (2 Each of the following M lines contains three integers A, B and C (1 Each city is an endpoint for at most 10 roads. There will never be more than one road directly connecting a single pair of cities.

Output should consist of a single integer, the smallest total cost as described in the problem statement.