#include<cstdio>
#include<algorithm>
using namespace std;
const int nmax = 200005;
const int mmax = 400005;
int n,m,i,f[nmax],a[nmax],b[nmax],x,y,cost,cnt;
struct muchie {int x,y,c;} e[mmax];
bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}
int find(int x)
{
    if(x!=f[x]) f[x]=find(f[x]);
    return f[x];
}
void unite(int x,int y)
{
    f[x]=y;
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
	for(i=1;i<=n;i++) f[i]=i;
	sort(e+1,e+m+1,cmp);
	for(i=1;i<=m;i++)
	{
	    x=find(e[i].x); y=find(e[i].y);
	    if(x==y) continue;
	    cost+=e[i].c; cnt++;
	    a[cnt]=e[i].x; b[cnt]=e[i].y;
	    unite(x,y);
	}
	printf("%d\n%d\n",cost,cnt);
	for(i=1;i<=cnt;i++) printf("%d %d\n",a[i],b[i]);
	return 0;
}