#include<fstream>
#include<algorithm>
using namespace std;ifstream fin("apm.in");ofstream fout("apm.out");struct g{int x,y,c;}v[200001];int p[400001],t[400001],nr,s,n,m;bool cmp(g i,g j){return i.c<j.c;}int G(int x){return t[x]==x?x:(t[x]=G(t[x]));}void U(int x,int y){t[G(x)]=G(y);}int main(){fin>>n>>m;for(int i=1;i<=m;i++)fin>>v[i].x>>v[i].y>>v[i].c;sort(v+1,v+m+1,cmp);for(int i=1;i<=n;i++)t[i]=i;for(int i=1;i<=m;i++)if(G(v[i].x)!=G(v[i].y)){p[++nr]=i,s+=v[i].c;U(v[i].x,v[i].y);}fout<<s<<'\n'<<nr<<'\n';for(int i=1;i<=nr;i++)fout<<v[p[i]].x<<' '<<v[p[i]].y<<'\n';return 0;}