题目描述

战争时期，前线有 $n$ 个哨所，哨所之间通过 $m$ 条双向通信线路连接，每条线路传递信息需要花费固定的天数。

指挥部设在第 $1$ 个哨所。当指挥部下达命令后，信会通过通信线路同时向所有相连的哨所传递；每个收到信的哨所也会立即向其相连的其他哨所传递。

请计算：所有 $n$ 个哨所都收到命令所需的最短时间（即从指挥部到最远哨所的最短传递时间）。若存在哨所无法收到命令，输出 $-1$。

输入格式

第一行包含两个整数 $n, m$，分别表示哨所数量和通信线路数量。

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

输出格式

输出一行一个整数，表示完成送信的最短时间；若有哨所无法收到命令，输出 $-1$。

样例

4 4
1 2 4
2 3 2
3 4 5
1 3 7

11

样例解释
从指挥部 $1$ 出发，到 $2$ 的最短时间为 $4$，到 $3$ 的最短时间为 $7$（直接 $1\to 3$ 或 $1\to 2\to 3$ 取 $\min(7, 6)=6?$ 这里选 $1\to 3$ 是 $7$，实际上 $1\to 2\to 3$ 总时间 $4+2=6$，更短，故到 $3$ 最短为 $6$，到 $4$ 最短为 $\min(1\to 2\to 3\to 4 = 4+2+5=11, 1\to 3\to 4 = 7+5=12) = 11$。所以最远距离为 $11$，故所有哨所收到命令的最短时间为 $11$。

注：样例中的图连通，不存在无法到达的哨所。

数据范围

• $1 \le n \le 100$
• $1 \le i, j \le n$
• $1 \le k \le 10^4$