#include<fstream>
#include<vector>
#include<algorithm>
#define MAX 400100
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie {int x, y, c;};
muchie v[MAX];
int n, m, ct, s[MAX], v1[MAX], v2[MAX], k;
bool comp (muchie i, muchie j)
{return (i.c < j.c);}
int sel(int t)
{if (s[t] == t) return t;
 s[t]=sel(s[t]);
 return s[t];
}
void reuniune(int i, int j)
{s[sel(i)] = sel(j);}
int main()
{f>>n>>m;
 for(int i=1;i<=m;i++)
	{f>>v[i].x>>v[i].y>>v[i].c;}
 for(int i=1;i<=n;i++) s[i]=i;
 sort(v + 1,v + m + 1,comp);
 for(int i=1;i<=m;i++)
    if(sel(v[i].x)!=sel(v[i].y))
	   {ct+=v[i].c;  v1[++k]=v[i].x; v2[k]=v[i].y;
	    reuniune(v[i].x, v[i].y);
	   }
 g<<ct<<"\n"<<n-1<<"\n";
 for(int i=1;i<=n-1;i++) g<<v1[i]<<" "<<v2[i]<<'\n';
 g.close();
 return 0;
}