#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;}