【题目描述】

北冰洋有一座孤岛，多年来一直没电。近日，令岛民们振奋的消息传来：S国的专家要为他们修建电网！！！

孤岛上共有N个村庄，发电站要建在第K个村庄中。S国的专家要在N个村庄间修建M条输电线路，但由于地理原因，M条线路无法保证每个村庄都与第K个村庄(建有发电站)直接相连，同样，也不一定能保证每个村庄都与第K个村庄间接相连(假设A与B直接相连，B与C直接相连，那么A与C间接相连)。

然而，由于S国的专家智商实在太“高”了，以至于设计出了许多冗余线路。现给出第i条线路两个端点Ui,Vi(分别表示线路连接的两个村庄,Ui!=Vi)和长度Li，请你帮岛民算一下：如果电网可以覆盖全岛，最少需要多长的电线；若不能，有多少个村庄无电可用。

注意：0<=冗余线路数目<M；部分数据有重边。电网可双向导电。

【输入格式】

第一行：N M K

接下来M行：Ui Vi Li

具体含义见题目描述

【输出格式】

如果电网可以覆盖全岛，输出最少需要的电线长度；

若不能，输出无电可用的村庄的个数。

【输入样例1】

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

【输出样例1】

4

【输入样例2】

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

【输出样例2】

3

【样例解释】

对于样例一，电网可以覆盖全岛，最短长度为4；

对于样例二，电网无法覆盖3,4,5这3个村庄。

【数据范围】

对于20%的数据，有1<M,N<=10;

对于60%的数据，有1<M,N<=1000;

对于100%的数据，有1<M,N<=200000,0<Li<=1E+7;

对于40%的数据，电网无法覆盖全岛。