问题描述

作为一位繁忙的程序员，小蓝经常需要在 $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→2$，需要电量 $3$。

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

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

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

从 $2$ 到 $4$ 可以走：$2→4$，需要电量 $2$。

从 $3$ 到 $4$ 可以走：$3→4$，需要电量 $2$。

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

评测用例规模与约定

对于 $20\%$ 的数据，$1≤N,M≤100$，$0≤w_i≤100$。

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