思路：kruskal3遍

样例：AC

结果：15pt

#include<bits/stdc++.h>
#define int long long
using namespace std;
int father[20100];
int fa[20010];
struct node{
	int u, v, w, is;
}edge[100010];
int find(int index) {
	if(father[index] == index) return index;
	return father[index] = find(father[index]);
}
int find2(int index) {
	if(fa[index] == index) return index;
	return fa[index] = find(fa[index]);
}
int cnt = 0;
bool cmp(node x, node y) {
	return x.w > y.w;
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m, k; cin >> n >> m >> k;
	for(int i=1; i<=m; ++i) cin >> edge[i].u >> edge[i].v >> edge[i].w;
	for(int i=1; i<=n; ++i) {
		fa[i] = i;
	}
	for(int i=1; i<=n; ++i) {
		father[i] = i;
	}
	cnt = 0;
	int cnt2 = 0;
	for(int i=1; i<=m; ++i) {
		if(edge[i].w == 0) {
			if(find(edge[i].u) != find(edge[i].v)) {
				father[find(edge[i].u)] = find(edge[i].v);
			}
		}
	}
	for(int i=1; i<=m; ++i) {
		if(edge[i].w == 1) {
			if(find(edge[i].u) != find(edge[i].v)) {
				edge[i].is = 1;
				father[find(edge[i].u)] = find(edge[i].v);
				fa[find2(edge[i].u)] = find2(edge[i].v);
				cnt ++;
			}
		}
	}
	cnt2 = cnt;
	if(cnt > k) {
		cout << "no solution";
		return 0;
	}
	for(int i=1; i<=n; ++i) {
		father[i] = i;
	}
	cnt = 0;
	for(int i=1; i<=m; ++i) {
		if(edge[i].w == 1) {
			if(find(edge[i].u) != find(edge[i].v)) {
				father[find(edge[i].u)] = find(edge[i].v);
			}
		}
	}
	for(int i=1; i<=m; ++i) {
		if(edge[i].w == 0) {
			if(find(edge[i].u) != find(edge[i].v)) {
				edge[i].is = 1;
				father[find(edge[i].u)] = find(edge[i].v);
				fa[find2(edge[i].u)] = find2(edge[i].v);
				cnt ++;
			}
		}
	}
	if(cnt > n-k-1) {
		cout << "no solution";
		return 0;
	}
	sort(edge+1, edge+1+m, cmp);
	int ct = cnt + cnt2;
	for(int i=1; i<=m; ++i) {
		if(ct == n-1) {
			if(cnt2 < k) {
				cout << "no solution";
				return 0;
			}
			break;
		}
		if(find2(edge[i].u) != find2(edge[i].v) && !edge[i].is) {
			if(edge[i].w && cnt2 < k) {
				fa[find2(edge[i].u)] = find2(edge[i].v);
				cnt2++;
				edge[i].is = 1;
				ct++;
			}
			if(!edge[i].w && ct - cnt2 <  n-k-1) {
				fa[find2(edge[i].u)] = find2(edge[i].v);
				ct++;
				edge[i].is = 1;
			}
		}
	}
	if(ct < n-1  ||  cnt2 != k) {
		cout << "no solution";
		return 0;
	}
	for(int i=1; i<=m; ++i) {
		if(edge[i].is) {
			cout << edge[i].u << " " << edge[i].v << " " << edge[i].w << endl;
		}
	}
	return 0;
}