WA 57pts悬2关求条

#include <bits/stdc++.h>
using namespace std;
#define debug cerr<<"The code runs successfully.\n";
#define endl '\n'
#define TRACE 1
#define tcout TRACE && cout
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define fir first
#define sec second
const int P = 998244353; 
const int Base = 33331;
#ifdef int
const int INF = 0x3f3f3f3f3f3f3f3f; 
#else
const int INF = 0x3f3f3f3f;
#endif
const int N = 1e5 + 10, M = 1e6 + 10;
int f[N];
int n,m,k;
struct Node {
	int u,v,w;
}a[N];
inline int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
inline void init() {
	for(int i=1;i<=n;i++) f[i]=i;
}
inline bool cmp1(Node x,Node y) {
	return x.w<y.w;
}
inline bool cmp2(Node x,Node y) {
	return x.w>y.w;
}
vector<Node> ans;
signed main() {
	fst;
	cin>>n>>m>>k;
	k=(n-1)-k;
	for(int i=1;i<=m;i++) {
		cin>>a[i].u>>a[i].v>>a[i].w;
	}
	int cnt=0;
	init();
	sort(a+1,a+1+n,cmp1);
	for(int i=1;i<=m;i++) {
		int u=a[i].u,v=a[i].v;
		if(find(u)!=find(v)) {
			cnt++;
			f[find(u)]=find(v);
			if(a[i].w==1) k--,a[i].w=2;
		}
	}
	if(cnt<n-1||k<0) {
		cout<<"no solution"<<endl;
		return 0;
	}
	sort(a+1,a+1+n,cmp2);
	init();
	cnt=0;
	//cerr<<k<<endl;
	for(int i=1;i<=m;i++) {
		int u=a[i].u,v=a[i].v;
		if(a[i].w==2) {
			if(find(u)!=find(v)) {
				f[find(u)]=find(v);
				cnt++;
				ans.push_back({u,v,1});
			}
		}
		else if(a[i].w==1) {
			if(find(u)!=find(v)) {
				if(k>0) {
					f[find(u)]=find(v);
					cnt++;
					k--;
					ans.push_back({u,v,1});
				}
			}
		}
		else {
			if(find(u)!=find(v)) {
				f[find(u)]=find(v);
				cnt++;
				ans.push_back({u,v,0});
			}
		}
	}
	if(k>0||cnt<n-1) {
		//cerr<<k<<endl;
		cout<<"no solution"<<endl;
		return 0;
	}
	for(auto e:ans) {
		cout<<e.u<<" "<<e.v<<" "<<e.w<<endl;
	}
	return 0;
}