Description

During wartime, there are n outposts on the front line, and each outpost may have communication links with several other outposts. Messengers are responsible for delivering messages between outposts, which naturally takes a certain amount of time (measured in days).

The headquarters is located at the first outpost. When the headquarters issues an order, it dispatches several messengers to deliver the message to the outposts connected to it. Once an outpost receives the message, the messengers within that outpost proceed to deliver the message to other outposts in the same manner. This process continues until all n outposts have received the order, at which point the delivery is considered successful.

Due to thorough preparations, each outpost is equipped with enough messengers (if an outpost has communication links with k other outposts, it will have at least k messengers). Now, the commander-in-chief asks you to write a program to calculate the minimum time required to complete the entire message delivery process.

Input Format

• The first line contains two integers, n and m, separated by a single space, representing the number of outposts (n) and the number of communication lines (m), where 1 ≤ n ≤ 100.
• Lines 2 to m+1: Each line contains three integers i, j, and k, separated by a single space, indicating that there is a communication line between the i-th and j-th outposts, and it takes k days to traverse this line.

Output Format

A single integer representing the shortest time required to complete the entire message delivery process. If not all outposts can receive the message, output -1.

4 4
1 2 4
2 3 7
2 4 1
3 4 6

11