#import <bits/stdc++.h>
#define z int
using namespace std;ifstream f("apm.in");ofstream g("apm.out");struct s{z x,y,c;}v[5e5];z t[5e5];s r[5e5];z o(s a, s b){return a.c<b.c;}z w(z h){if(t[h]==h)return h;return t[h]=w(t[h]);}void j(z x, z y){x=w(x);y=w(y);t[x]=y;}z main(){z n,m,x,y,c,i,l=0,V=0;f>>n>>m;for(i=0;i<n;i++)t[i]=i;for(i=0;i<m;i++){s a;f>>x>>y>>c;x--;y--;a.x=x;a.y=y;a.c=c;v[i]=a;}sort(v,v+m,o);for(i=0;i<m;i++)if(w(v[i].x)!=w(v[i].y)){j(v[i].x,v[i].y);r[l++]=v[i];V+=v[i].c;}g<<V<<'\n'<<n-1<<'\n';for(i=0;i<n-1;i++)g<<r[i].x+1<<" "<<r[i].y+1<<'\n';return 0;}