#include<cstdio>
#include<vector>
#include<algorithm>
#define Max 400100
using namespace std;
vector<int>v;
int nr,rez,i,j,m,n,t[Max],gr[Max],x[Max],y[Max],c[Max],ind[Max];
bool comp(int i,int j){return c[i]<c[j];}
int vf(int x)
{
    while(t[x]!=x) x=t[x];
    return x;
}
void unire(int x,int y)
{
    if(gr[x]>gr[y]) t[y]=x;
    else if(gr[x]<gr[y]) t[x]=y;
    else{t[y]=x; ++gr[x];}
}

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; t[i]=i;
    }
    sort(ind+1,ind+m+1,comp);
    nr=0; i=0;
    for(i=1;i<=m;++i)
    {
        int _i=vf(x[ind[i]]),_j=vf(y[ind[i]]);
        if(_i!=_j)
        {
            unire(_i,_j);
            rez+=c[ind[i]];
            v.push_back(ind[i]);
        }
    }
    printf("%d\n%d\n",rez,n-1);
    for(i=0;i<n-1;++i) printf("%d %d\n",x[v[i]],y[v[i]]);
    return 0;
}