CF1184E1 DALEKS' INVASION (EASY)
题目描述
Heidi 发现 Daleks 创建了一个由双向时间通道连接不同目的地（在不同时间！）的网络。她怀疑他们正计划对整个时空进行又一次入侵。为了反制入侵，她打算在时间漩涡中沿着精心挑选的时间通道布置陷阱。她知道干涉时间漩涡很危险，于是咨询了 Doctor 的意见。她了解到如下信息：
* 不同的时间通道需要不同的能量来保持稳定。
* Daleks 在入侵时不太可能使用所有通道。他们会选择一组总能量消耗最小、但仍能保证任意两个目的地之间可以（通过时间）到达的通道（对于熟悉的人来说：他们会选择一棵最小生成树）。
* 布置陷阱可能会改变该通道所需的能量。
Heidi 决定进行实地测试，并在第一条通道上布置一个陷阱。但她需要知道，在布置陷阱后 Daleks 是否还会使用这条通道。
她给了你一张时间通道的地图（一个无向图），每条通道都有对应的能量需求。
对于一条通道 ccc，Emax(c)E_{max}(c)Emax (c) 表示最大的 e≤109e \le 10^9e≤109，使得如果我们将 ccc 的能量需求改为 eee，那么 Daleks 仍有可能在入侵时使用 ccc（即 ccc 属于某棵最小生成树）。你的任务是计算 Heidi 计划布置陷阱的第一条通道 c1c_1c1 的 Emax(c1)E_{max}(c_1)Emax (c1 )。
输入格式
第一行包含两个整数 nnn 和 mmm（2≤n≤1052 \leq n \leq 10^52≤n≤105，n−1≤m≤106n-1 \leq m \leq 10^6n−1≤m≤106），分别表示目的地数量和时间通道数量。
接下来的 mmm 行，每行描述一条通道：目的地 aaa、bbb 以及能量 eee（1≤a,b≤n1 \leq a, b \leq n1≤a,b≤n，a≠ba \neq ba=b，0≤e≤1090 \leq e \leq 10^90≤e≤109）。
保证没有重复的 {a,b}\{a, b\}{a,b} 对，并且图是连通的——即任意两个目的地之间都可以通过若干条时间通道到达。
输出格式
输出一个整数：第一条通道 c1c_1c1 的 Emax(c1)E_{max}(c_1)Emax (c1 )。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
布置陷阱后，第一条通道的能量需求可能变小、变大或保持不变。
例如，在样例中，如果第一条通道的能量被设置为 444 或更小，则 Daleks 可能会选择通道集合 {{1,2},{2,3}}\{\{1,2\}, \{2,3\}\}{{1,2},{2,3}}（特别地，如果设置为小于 444，那么这将是唯一的选择）。然而，如果能量大于 444，他们则会选择通道集合 {{2,3},{3,1}}\{\{2,3\}, \{3,1\}\}{{2,3},{3,1}}。
答案：
