题目描述

科学家正在研究一种新型病毒的传播规律。实验室里培养了 $n$ 个细胞样本，编号 $1$ 到 $n$。其中 $1$ 号样本被注入了病毒。

病毒可以通过细胞之间的通道传播：

当一个细胞被感染后，它会立即通过所有通道向相邻细胞传播病毒

每条通道的传播需要一定的时间（以小时为单位）

实验室的监控设备记录了所有通道的连接关系。

请问：从开始实验到所有细胞都被感染，最短需要多少小时？如果存在无法被感染的细胞，输出 $-1$。

输入格式

第一行两个整数 $n$ 和 $m$，表示有 $n$ 个细胞和 $m$ 条传播通道。

接下来 $m$ 行，每行三个整数 $a, b, h$，表示细胞 $a$ 和细胞 $b$ 之间有传播通道，传播需要 $h$ 小时。

输出格式

输出一个整数，表示所有细胞都被感染的最短时间。如果存在无法被感染的细胞，则输出 $-1$。

输入输出样例

输入 #1

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

输出 #1

11

样例解释

数据范围

• $1 \le n \le 100$
• $1 \le m \le \frac{n(n-1)}{2}$
• $1 \le k \le 10^4$