#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int gr[200001],x[400001],y[400001],c[400001];
int i,n,M,cost=0,ind[400001];
vector<int> much;
int grupa(int i)
{
    if(gr[i]==i) return i;
    gr[i]=grupa(gr[i]);
    return gr[i];
}
void reuniune(int i,int j)
{
    gr[grupa(i)]=grupa(j);
}
bool cmpf(int i, int j)
{   
    return (c[i]<c[j]);
}
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",&x[i],&y[i],&c[i]);
        ind[i]=i;
    }
    for(i=1;i<=n;++i) gr[i]=i;
    sort(ind+1,ind+M+1,cmpf);
    for(i=1;i<=M;++i)
    {
        if(grupa(x[ind[i]])!=grupa(y[ind[i]]))
        {
            cost+=c[ind[i]];
            reuniune(x[ind[i]],y[ind[i]]);
            much.push_back(ind[i]);
        }
    }
    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(i=0;i<n-1;++i)
        printf("%d %d\n",x[much[i]],y[much[i]]);
    return 0;
}