某电信公司在一条山区公路沿线建设了 N 个通信基站。这些基站通过 M 条光纤链路相互连接，第 i 条链路连接基站 U_i 和 V_i（U_i \neq V_i），链路长度为 L_i 公里，该网络是连通的，且对于任意的两个基站，它们之间最多只有一条链路相连。
电信公司决定将所有基站分配到两个频段（频段 1 和频段 2）中使用。
分配要求如下：对于使用同一频段的任意两个不同基站，它们之间通过光纤链路的最短路径（链路长度之和最小的那条路径）的总长度必须至少为 X 公里。
请计算最大的整数 X，使得存在一种分配方案满足上述要求。
第一行包含两个整数 N 和 M。
接下来 M 行，每行包含三个整数 U_i、V_i 和 L_i，表示一条链路的两个端点基站和长度。
输出一个整数，表示最大的 X 值。
3 3 1 2 5 2 3 6 1 3 12
11
10 20 7 10 982219000 3 10 968366179 2 4 992330437 5 6 984414664 2 8 897295423 7 9 155604979 6 8 958833005 2 3 973209957 3 7 985173062 6 10 963895817 2 10 986243534 4 5 721724794 1 3 657562445 1 6 566370694 1 4 988050146 1 9 967817807 4 9 796531581 5 9 983960054 1 10 964450079 8 9 959369491
952136560
10 20 5 6 871895994 8 10 873709822 3 5 454175869 6 10 980782191 2 6 901290987 1 8 298092290 4 8 693116157 4 5 947939338 7 8 934395075 7 9 759563833 5 8 779870031 4 6 919637355 2 9 822858749 4 10 855497285 3 7 954942051 1 2 950411658 4 7 665939990 3 4 634533617 5 7 908372507 1 9 591466693
759563833
将基站 1 和 3 分配到同一频段，基站 2 分配到另一频段。此时，同一频段内的基站 1 和 3 之间的最短路径长度为 \min(12, 5+6)=11，满足 X=11 的要求。
若 X=12，则基站 1 和 3 的最短路径长度为 11 \lt 12，不能分配到同一频段；基站 1 和 2 的路径长度为 5 \lt 12，基站 2 和 3 的路径长度为 6 \lt 12。任意两个基站都不能分配到同一频段，但只有两个频段，无法完成分配。因此 11 是最大可能值。
对于 100\% 的数据，满足 3 \leq N \leq 2 \times 10^5，N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2 \times 10^5\right)，1 \leq U_i \lt V_i \leq N，1 \leq L_i \leq 10^9，给定的图是简单连通无向图。
| 测试点编号 | N,M | 特殊性质 |
|---|---|---|
| 1 | 1 \le N \le 20，M=N-1 | A |
| 2 | 1 \le N,M \le 20，N=M | B,C |
| 3 \sim 4 | 1 \le N,M \le 2 \times 10^5，N=M | B |
| 6 \sim 10 | 1 \le N,M \le 2 \times 10^5 | 无 |
特殊性质 A：测试数据保证 U_i = i, V_i = i + 1，L_i=1。即：图构成一条从左向右的编号依次为 1 2 3 \dots N 的链。
特殊性质 B：测试数据保证，对于 2 \le i \le N-1 的点，满足编号为 i 的点和编号为 i-1 的点以及编号为 i+1 的点分别有一条链路相连，编号为 1 的点和编号为 N 的点有一条链路相连。即：图构成一个环。
特殊性质 C：测试数据保证，所有的 L_i 全部相等。