Shortest Escape Distance

You are given a mine consisting of n rooms (numbered from 1 to n) and m bidirectional corridors. Each corridor connects two rooms and has an associated distance.

The miner starts in room 1. In order to escape the mine, the miner can exit from any corridor by reaching one of its endpoints and then using that corridor as an escape route. Formally, for every corridor connecting room u and room v with distance w, the miner can potentially escape by traveling from room 1 to u (or v) and then taking the corridor of length w. Your task is to determine the minimum total distance the miner must travel to escape the mine.

If it is not possible to escape (for instance, when there are no corridors or when the mine consists of a single room), output INF.

Note: All corridors are undirected and can be used in both directions.

inputFormat

The first line contains two integers n and m — the number of rooms and corridors.

Each of the next m lines contains three integers u v w, representing a corridor connecting room u and room v with distance w.

It is guaranteed that all input values are separated by spaces and/or newlines.

outputFormat

Output a single line containing the minimum distance the miner must travel to escape the mine. If it is not possible for the miner to escape, output INF.

5 6
1 2 3
1 3 2
2 3 4
2 4 3
3 4 1
4 5 6

2