T454244 「2024 百度之星选拔赛」魔女们的舞踏会


魔理沙最近在红魔馆大图书馆中~~偷偷~~看书时，偶然间看到了有关无向图中最小生成树的魔法。 这个魔法的操作如下： - 任意选择图中的一条边 $(u, v)$，然后将除了这条边以外的所有边边权都减少 $1$。 - 每次施加魔法选择的边可以不同。 魔理沙想要通过施加若干次这个魔法，以确保图中的边 $(S, T)$ 出现在此无向图的最小生成树中。 边 $(S, T)$ 的编号为 $k$。 请求出魔理沙至少需要施加多少次魔法才可以保证边 $(S, T)$ 在最小生成树中。

第一行输入三个整数 $n, m, k$ $\;$ ($1 \le n \le 500, 1 \le m \le 800, 1 \le k \le m$)，分别表示无向图中点的个数、边的条数和边 $(S, T)$ 的编号。 接下来 $m$ 行，每行三个整数 $u, v, w$ $\;$ ($1 \le u, v \le n, u\not = v$, $1 \le w \le 10^6$)，表示 $u$ 和 $v$ 之间有一条边权为 $w$ 的无向边。 边的编号从 $1 \sim m$。数据保证无向图连通。

输出一行一个整数，表示使得编号为 $k$ 的边，即边 $(S, T)$ 确保存在于最小生成树中的最少魔法操作次数。

### 样例解释 可以选择边 $(2, 4)$ 施加一次魔法，使得编号为 $2$ 的边，也就是边 $(1, 2)$ 确保存在于最小生成树中。