[SHOI2010]最小生成树

题目描述

Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个 $ n $ 个点、 $ m $ 条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外,他还知道,某一个图可能有多种不同的最小生成树。例如,下面图3中所示的都是图2中的无向图的最小生成树: ![](https://cdn.luogu.com.cn/upload/pic/43631.png) 当然啦,这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB,至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中,你可以对这个无向图进行操作,一次单独的操作是指:先选择一条图中的边 P1P2,再把图中除了这条边以外的边,每一条的权值都减少 $ 1 $ 。如图4所示就是一次这样的操作: ![](https://cdn.luogu.com.cn/upload/pic/43632.png)

输入输出格式

输入格式


输入文件的第一行有3个正整数 $ n,m,Lab $ 分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。 接下来 $ m $ 行依次描述标号为 $ 1,2,3 \ldots m $ 的无向边,每行描述一条边。每个描述包含3个整数 $ x,y,d $ ,表示这条边连接着标号为 $ x,y $ 的点,且这条边的权值为 $ d $ 。 输入文件保证 $ 1 \leq x,y \leq N $ , $ x \neq y $ ,且输入数据保证这个无向图一定是一个连通图。

输出格式


输出文件只有一行,这行只有一个整数,即,使得标号为 $ Lab $ 边一定出现最小生成树中的最少操作次数。

输入输出样例

输入样例 #1

4 6 1
1 2 2
1 3 2
1 4 3
2 3 2
2 4 4
3 4 5

输出样例 #1

1

说明

$ 1 \leq N \leq 500,1 \leq M \leq 800,1 \leq d<10^6 $