题目描述

战争时期，前线有 $n$ 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，通信需要花费一定时间。

指挥部设在第 $1$ 个哨所。当指挥部下达命令后，收到命令的哨所会继续把命令传给与它相连的其他哨所。请计算让所有哨所都收到命令的最短时间。

输入格式

第一行输入两个整数 $n,m$，表示哨所数量和通信线路数量。

接下来 $m$ 行，每行输入三个整数 $i,j,k$，表示第 $i$ 个哨所和第 $j$ 个哨所之间有一条通信线路，传递需要 $k$ 天。

输出格式

输出一个整数，表示完成整个送信过程的最短时间。如果不是所有哨所都能收到信，输出 -1。

样例

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

11

数据范围

对于全部数据，满足 $1 \le n \le 100$，$1 \le m <= 200, 1 <= k <= 1000$，线路耗时为正整数。