#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define inf 10000000 #define maxn 21 int m,n; int edge[maxn][maxn],lowcost[maxn],nearvex[maxn]; void prim(int u0) { int i,j; int sumweight=0; for(i=1; i<=n; i++) { lowcost[i]=edge[u0][i]; nearvex[i]=u0; } nearvex[u0]=-1; for(i=1; i<n; i++) { int min=inf; int v=-1; for(j=1; j<=n; j++) { if(nearvex[j]!=-1 && lowcost[j]<min) { v=j; min=lowcost[j]; } } if(v!=-1) { cout<<nearvex[v]<<" "<<v<<" "<<lowcost[v]<<endl; nearvex[v]=-1; sumweight+=lowcost[v]; for(j=1; j<=n; j++) { if(nearvex[j]!=-1 && edge[v][j]<lowcost[j]) { lowcost[j]=edge[v][j]; nearvex[j]=v; } } } } cout<<"weight of mst is "<<sumweight<<endl; } int main() { ios::sync_with_stdio(false); freopen("1.txt","r",stdin); int i,j,w,u,v; cin>>n>>m; memset(edge,0,sizeof(edge)); for(i=1; i<=m; i++) { cin>>u>>v>>w; edge[u][v]=edge[v][u]=w; } for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(i==j) edge[i][j]=0; else if(edge[i][j]==0) edge[i][j]=inf; } } prim(1); return 0; } /* 7 9 1 2 28 1 6 10 2 3 16 2 7 14 3 4 12 4 5 22 4 7 18 5 6 25 5 7 24 */