#import <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int N=5e5;struct s{int x,y,c;}v[N];int t[N];s ras[N];bool cmp(s a, s b){return a.c<b.c;}int tata(int nod){if(t[nod]==nod)return nod;return t[nod]=tata(t[nod]);}void join(int x, int y){x=tata(x);y=tata(y);t[x]=y;}int main(){int 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(tata(v[i].x)!=tata(v[i].y)){join(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;}