题目描述

当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB，至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边<v:shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"> P1P2<v:stroke joinstyle="miter"></v:stroke><v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"></v:f> <v:f eqn="sum @0 1 0"></v:f> <v:f eqn="sum 0 0 @1"></v:f> <v:f eqn="prod @2 1 2"></v:f> <v:f eqn="prod @3 21600 pixelWidth"></v:f> <v:f eqn="prod @3 21600 pixelHeight"></v:f> <v:f eqn="sum @0 0 1"></v:f> <v:f eqn="prod @6 1 2"></v:f> <v:f eqn="prod @7 21600 pixelWidth"></v:f> <v:f eqn="sum @8 21600 0"></v:f> <v:f eqn="prod @7 21600 pixelHeight"></v:f> <v:f eqn="sum @10 21600 0"></v:f> </v:formulas><v:path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></v:path><o:lock aspectratio="t" v:ext="edit"></o:lock> </v:shapetype>，再把图中除了这条边以外的边，每一条的权值都减少1。如图 4所示就是一次这样的操作：

输入格式

输出格式

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

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

1

数据范围与约定

第1个样例就是问题描述中的例子。

1<=n<=500,1<=M<=800,1<=D<10^6