题目描述

A 国的边境上修建了 $n$ 座兵营（编号为 $1$~$n$ ），某些兵营之间修建了用于传达消息的双向道路，不同的道路由于长度和平整度不同，也就可能需要不同的天数才能走完。

为方便指挥作战，A国将指挥所修建在了 $1$ 号兵营。当指挥部下达作战指令后，指挥部就派出若干个传令兵，按照预先修好的道路，将指令传达给相邻的兵营。当一座兵营接到指令后，会按同样的方式向其他兵营传达指令，直到所有的兵营都收到作战指令。

请编程计算出，从指挥部发出作战指令到所有兵营都收到作战命令，最短需要多少天。

输入格式

第一行有两个整数 $n$ 和 $m$ ，表示有 $n$ 个兵营和 $m$ 条道路。

第 $2$ 至 $m+1$ 行，每行三个整数 $x,y,k$，表示第 $x$ 个和第 $y$ 个兵营之间存在一条需要 $k$ 天才能走完的双向道路。

本题数据保证任意两个兵营之间最多只有一条道路。

数据范围

$1 \le n \le 100$

$1 \le m \le 500$

$1 \le x,y \le n$

$1 \le k \le 1000$

输出格式

输出所有兵营接到指令的最短天数，如果由于道路的缺失，导致无论如何都不能做到所有兵营都能接到指令，请输出 $-1$

样例

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

11