题目描述

作为一名繁忙的程序员，小蓝经常需要在 $N$ 座城市之间来回穿梭。他准备购买一辆电动车出行，但是担心电动车电量不足。

为了描述方便，我们把 $N$ 座城市编号 $1$ 至 $N$。城市之间一共有 $M$ 条双向高速公路相连。其中第 $i$ 条连接 $u_i$ 号城市和 $v_i$ 号城市，耗费 $w_i$ 个单位的电量。

假设小蓝可以在出发城市，以及任何中途经过的城市充满电。小蓝想知道，如果希望从任意城市开电动车到任意另一个城市，都可以找到一条由若干高速公路组成路径，使得不需要在任何高速公路内补充电量，那么这台电动车至少需要多少电量？

输入格式

第一行包含两个整数 $N$ 和 $M$。

以下 $M$ 行，每行包含 $3$ 个整数 $u_i$、$v_i$ 和 $w_i$。

输出格式

一个整数，代表答案。

如果存在两个城市不能通过高速公路相互到达，输出 $-1$。

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

3

提示

样例说明

• 从 $1$ 到 $2$ 可以走：$1 \rightarrow 2$，需要电量 3。
• 从 $1$ 到 $3$ 可以走：$1 \rightarrow 2 \rightarrow 4 \rightarrow 3$，其中 $1 \rightarrow 2$ 需要电量 $3$，$2 \rightarrow 4$ 需要电量 $2$，$4 \rightarrow 3$ 需要电量 $2$，全程至少需要电量 $3$。
• 从 $1$ 到 $4$ 可以走：$1 \rightarrow 2 \rightarrow 4$，其中 $1 \rightarrow 2$ 需要电量 $3$，$2 \rightarrow 4$ 需要电量 $2$，全程至少需要电量 $3$。
• 从 $2$ 到 $3$ 可以走：$2 \rightarrow 4 \rightarrow 3$，其中 $2 \rightarrow 4$ 需要电量 $2$，$4 \rightarrow 3$ 需要电量 $2$，全程至少需要电量 $2$。
• 从 $2$ 到 $4$ 可以走：$2 \rightarrow 4$，需要电量 $2$。
• 从 $3$ 到 $4$ 可以走：$3 \rightarrow 4$，需要电量 $2$。

综上所述，电动车至少需要 $3$ 个单位的电量。

评测用例规模与约定

• 对于 $20\%$ 的数据，$1 \leq N, M \leq 100$，$0 \leq w_i \leq 100$。
• 对于 $100\%$ 的数据，$1 \leq N, M \leq 200000$，$0 \leq w_i \leq 10^9$。