NYOJテーマ925キングの悩み(最小生成木変形)

王様の悩み
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
2
説明
C国はn個の小島からなり、小島間の連絡を容易にするために、C国は小島間にm個の大橋を建設し、大橋ごとに2個の小島を接続した.2つの島の間には複数の橋が接続されている可能性があります.しかし、海水洗浄のため、一部の大橋は使用できない危険に直面している.2つの小島間のすべての大橋が使えないと、この2つの小島は直接到着できません.しかし、この2つの島の住民が他の橋や他の島を通って互いに到着すれば、彼らは無事になる.しかし、前日に2つの島の間に到着する方法があり、翌日に到着できない場合、住民たちは一緒に抗議します.
現在、C国の王は橋ごとに使える日数を知っていますが、この日数を超えると使えません.今、彼は住民たちが何回抗議するか知りたい.
入力
複数のテストデータ.
各データのセットには、まず2つの正の整数nとmが入力される.
次にm行、各行の3つの整数a,b,tは、それぞれこの橋がa号とb号の2つの小島を接続していることを示し、t日を使用することができる.小島の番号は1から増えていく.(1≤n≤10000,1≤m≤100000,1<=a,b<=n,1≤t≤100000)
しゅつりょく
住民たちが抗議した回数を示す整数を出力します.
サンプル入力

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

サンプル出力

2

ヒント
サンプルの場合:
1日目以降は2と3の間の橋は使えず、影響しません.
翌日1と2の間、そして1と3の間の橋が使えなくなり、住民たちは抗議します.
3日目以降は3と4の間の橋が使えず、住民たちが抗議します.
ソース
ブルーブリッジカップ
アップロード者
TC_李遠航
acコード

#include
#include
#include
#include
#include
using namespace std;
struct s
{
	int u,v,w;
}edge[100100];
int pre[100100],a[100010];
void init(int n)
{
	int i;
	for(i=0;i<=n;i++)
		pre[i]=i;
}
int cmp(s a,s b)
{
	return a.w>b.w;
}
int find(int x)
{
	if(x==pre[x])
		return pre[x];
	return pre[x]=find(pre[x]);
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int i;
		init(n);
		for(i=0;i