这题一看，不是一句话题意，不想做。。
题意就不说了吧。。
首先想到的肯定是最小生成树。。
然后我就想起了以前的某道题。。好吧，记不大清了。。
那么怎么做呢？
我一开始的想法是贪心替换。。
就是先把图构好，然后用0去换1
也就是先把全部1跑一次，然后把0跑一次，先把必要的0拿出来，然后再在剩下的0里面选替代1的。。
然后随手给自己的替代方法举了个反例。。
那怎么办呢
首先把，第一步中不要的0是肯定的，那么替代方法要改一改。。
那我们干脆在剩下的随便拿不就好了嘛，给他凑够k个，反正图肯定有解
感觉很对。。
于是就A了
#include<cstdio>
#include<cstring>
const int N=20005;
const int M=100005;
int n,m,k;
struct qq {int x,y,z;bool tf;//这条边要不要用 }s[M];int num;
void init (int x,int y,int z)
{
// printf("YES:%d %d %d\n",x,y,z);num++;s[num].tf=false;s[num].x=x;s[num].y=y;s[num].z=z;
}
qq e[M];int num1;//鹅卵石路
void init1 (int x,int y,int z)
{num1++;e[num1].tf=false;e[num1].x=x;e[num1].y=y;e[num1].z=z;
}
int f[N];
int find (int x) {
return f[x]==x?x:f[x]=find(f[x]);}
int main()
{num=num1=0;scanf("%d%d%d",&n,&m,&k);for (int u=1;u<=n;u++) f[u]=u;for (int u=1;u<=m;u++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if (z==1) init(x,y,z);else init1(x,y,z);}
// for (int u=1;u<=num;u++) printf("%d %d %d\n",s[u].x,s[u].y,s[u].z);for (int u=1;u<=num;u++)//先把沥青路都扫一遍 {int x=s[u].x,y=s[u].y;int fx=find(x),fy=find(y);if (fx==fy) continue;s[u].tf=true;f[fx]=fy;}for (int u=1;u<=num1;u++){int x=e[u].x,y=e[u].y;int fx=find(x),fy=find(y);if (fx==fy) continue;f[fx]=fy;e[u].tf=true;k--;}if (k<0) {
printf("no solution\n");return 0;}int ooo=find(1);for (int u=2;u<=n;u++)if (find(u)!=ooo){
printf("no solution\n");return 0;}for (int u=1;u<=n;u++) f[u]=u;for (int u=1;u<=num1;u++){if (e[u].tf==true) {int x=e[u].x,y=e[u].y;int fx=find(x),fy=find(y);f[fx]=fy;}}for (int u=1;u<=num1;u++){if (e[u].tf) continue;if (k<=0) break;int x=e[u].x,y=e[u].y;int fx=find(x),fy=find(y);if (fx==fy) continue;f[fx]=fy;k--;e[u].tf=true;}//printf("%d ",k);/*for (int u=1;u<=num1;u++)if (e[u].tf)printf("%d %d %d\n",e[u].x,e[u].y,e[u].z);*/for (int u=1;u<=num;u++) s[u].tf=false;for (int u=1;u<=num;u++){int x=s[u].x,y=s[u].y;int fx=find(x),fy=find(y);if (fx==fy) continue;f[fx]=fy;s[u].tf=true;}for (int u=1;u<=num;u++)if (s[u].tf)printf("%d %d %d\n",s[u].x,s[u].y,s[u].z);for (int u=1;u<=num1;u++)if (e[u].tf)printf("%d %d %d\n",e[u].x,e[u].y,e[u].z);return 0;
}