Messengers

Special for beginners, ^_^

Problem Description

During wartime there are $n$ outposts on the front line. Each outpost may be in communication with several other outposts. Messengers carry messages between outposts, which of course takes some time (measured in days). The headquarters is stationed at the first outpost. When headquarters issues an order, it sends several messengers to the outposts directly connected to it. Once an outpost receives a message, the messengers stationed there forward it to other outposts in the same way. The delivery succeeds only when all $n$ outposts have received the order. Because of careful preparation, each outpost has enough messengers (if an outpost communicates with $k$ other outposts, at least $k$ messengers are stationed there).

The commander-in-chief asks you to write a program that computes the minimum time needed to complete the whole delivery process.

Input Format

The first line contains two integers $n$ and $m$ separated by one space: there are $n$ outposts and $m$ communication lines. $1\le n\le100$.

Lines $2$ through $m+1$: each line has three integers $i,j,k$ separated by one space, meaning there is a communication line between outposts $i$ and $j$, and that line takes $k$ days.

Output Format

One integer: the minimum time for the whole delivery process. If not all outposts can receive the message, output $-1$.

Sample Input 1

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

Sample Output 1

11

Constraints

1s, 1024KiB for each test case.