题目描述

前线有 $n$ 个哨所，其中第 $1$ 个是指挥部。一些哨所之间有双向通信线路，每条线路有相应的送信时间。

指挥部在时刻 $0$ 下达命令，立即派信使向相邻哨所送信。每个哨所收到命令后，也立即派信使向相邻哨所送信。信使数量充足，可以同时沿多条线路送信。

求让所有哨所都收到命令的最短时间。如果有哨所无法收到命令，输出 $-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\le100$，$0\le m\le10000$，$1\le i,j\le n$，$i\ne j$，$1\le k\le100000$。