Migrated from Lutece 2549 土豆的社交

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

人都是需要社交的，就算是认真打 ACM 的集训队员也不例外，所以 $n$ 个集训队的队员之间形成了一张错综复杂的关系网。每两个成员之间可能存在社交关系，并且有一个好感度，这样的关系一共有 $m$ 对，集训队不存在孤儿，所以每位队员至少和另一位队员有关系。土豆作为集训队的交际花，可以通过一次操作（俗称拱火）来增加或降低 $1$ 点两个成员之间的好感度，当土豆完成所有操作之后，集训队员会开始组队，那些不喜欢社交的人就会断开绝大部分社交，直到任意两个集训队员之间只有一条社交通路可以连接彼此，换句话说，最后的关系网会变为有 $n-1$ 条边的关系树。土豆想让他和队友之间的羁绊成为集训队中最强的，而又不想集训队整体的关系太差，所以他希望最后的某个关系图中最大的某对好感度恰好等于给定的 $k$，请问懒狗土豆最少需要多少次操作来实现他的目标。

翻译：给定一个无向连通图，图中有 $n$ 个节点和 $m$ 条边，每次操作可以使某条边的边权增加或降低 $1$，问最少需要多少次操作可以使得图中某棵生成树的最大边权恰好等于给定值 $k$。

Input

第一行包含三个整数 $n,m,k$ 分别表示图中的结点数，边数，生成树中边权的最大值。

接下来 $m$ 行每行，每行包含三个整数 $u,v,w$，表示每条边连接的两个节点和它的边权。

Output

一个整数，表示需要的最小操作次数。

Samples

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

1

Constraints

$2\le n\le2\cdot 10^5,n-1\le m \le\min(2\cdot10^5,\frac{n(n-1)}{2} ),1\le k \le10^9$ $1\le u,v\le n, u\ne v,1\le w \le 10^9$

Resources

2021 UESTC ICPC Training for Graph