P12222 [蓝桥杯 2023 国 Java B] 电动车

作为一名繁忙的程序员，小蓝经常需要在 $N$ 座城市之间来回穿梭。他准备购买一辆电动车出行，但是担心电动车电量不足。 为了描述方便，我们把 $N$ 座城市编号 $1$ 至 $N$。城市之间一共有 $M$ 条双向高速公路相连。其中第 $i$ 条连接 $u_i$ 号城市和 $v_i$ 号城市，耗费 $w_i$ 个单位的电量。 假设小蓝可以在出发城市，以及任何中途经过的城市充满电。小蓝想知道，如果希望从任意城市开电动车到任意另一个城市，都可以找到一条由若干高速公路组成路径，使得不需要在任何高速公路内补充电量，那么这台电动车至少需要多少电量？

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

一个整数，代表答案。 如果存在两个城市不能通过高速公路相互到达，输出 $-1$。

### 样例说明 - 从 $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$。