C. [ABSEC0006] 太

这段旅程“太”过艰险。不仅路途遥远，某些山脉的风“太”过猛烈，让人无法承受。幸运的是，你拥有古老的护身符，可以为你抵挡几次风。

给定一个包含 个节点和 条边的无向连通图，节点编号为 到 。每条边有一个危险值 。

你需要从节点 出发走到节点 。

你的护身符允许你最多将 条途径边的危险值视为 。

一条路径的 “极限危险度” 定义为：该路径上经过的所有边中，危险值的最大值（被护身符抵消的边，其危险值视为 ）。

请你规划一条路径，使得从 走到 的“极限危险度”最小，并输出这个最小值。

第一行包含三个整数 (, )。

接下来 行，每行包含三个整数 ()，表示节点 和 之间有一条危险值为 的无向边。

输出一个整数，表示最小的“极限危险度”。

【样例输入】

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
3 4 7
4 5 6
2 5 9

【样例输出】

4

【样例说明】

存在一条路径为 1 -> 3 -> 2 -> 5，经过的边权依次为 4, 3, 9。

我们可以使用 1 次护身符（），将边权为 9 的边（即连接 2 和 5 的边）的危险值视为 0。

此时路径的危险值为 max(4, 3, 0) = 4。

可以证明这是极限危险度最小的方案。