#import <bits/stdc++.h>
using namespace std;
#define z int
ifstream f("apm.in");
ofstream g("apm.out");
const z N=500000;struct s{z x,y,c;}v[N];z t[N];s ras[N];bool cmp(s a, s b){return a.c<b.c;}z w(z nod){if(t[nod]==nod)return nod;return t[nod]=w(t[nod]);}void j(z x, z y){x=w(x);y=w(y);t[x]=y;}z main(){z n,m,x,y,c,i,cnt=0,suma=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,cmp);for(i=0;i<m;i++)if(w(v[i].x)!=w(v[i].y)){j(v[i].x,v[i].y);ras[cnt++]=v[i];suma+=v[i].c;}g<<suma<<'\n'<<n-1<<'\n';for(i=0;i<n-1;i++)g<<ras[i].x+1<<" "<<ras[i].y+1<<'\n';return 0;}