#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,t[200001],i,nrc,rg[200001],ales[400001],cost;
struct muchie
{
    int x,y,c;
};
muchie l[400001];
int cmp(muchie a,muchie b)
{
    return (a.c<b.c);
}
int rad(int x)
{
    int r,y;
	r=x;
    while(t[r]!=r)
        r=t[r];
    while(t[x]!=x)
    {
        y=t[x];
        t[x]=r;
        x=y;
    }
    return r;
}
int unite(int x,int y)
{
    nrc--;
    if(rg[rad(x)]>rg[rad(y)])
		t[rad(y)]=x;
    else
        t[rad(x)]=y;
    if (rg[rad(x)]==rg[rad(y)]) 
        rg[rad(y)]++;
    return 0;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
		f>>l[i].x>>l[i].y>>l[i].c;
    nrc=n;
    for(i=1;i<=n;i++)
	{
		t[i]=i;
		rg[i]=1;
    }
    i=1;
    sort(l+1,l+m+1,cmp);
    while(nrc>1)
    {
        while(rad(l[i].x)==rad(l[i].y))
            i++;
        unite(l[i].x,l[i].y);
        ales[++ales[0]]=i;
        cost+=l[i].c;
        i++;
    }
    g<<cost<<"\n"<<ales[0]<<"\n";
    for(i=1;i<=ales[0];i++)
		g<<l[ales[i]].x<<" "<<l[ales[i]].y<<"\n";
    return 0;
}