#include<stdio.h>
#include<algorithm>
#include<vector>
#define MAXM 401001

using namespace std;

int i,j,n,m,cost;
int X[MAXM],Y[MAXM],C[MAXM],ind[MAXM],TATA[MAXM/2];
vector<int> sol;

bool cmp(const int &a,const int &b)
{
    return C[a]<C[b];
}

int tata(int x)
{
    int y=x,z,aux;
    while(y!=TATA[y])
        y=TATA[y];
    z=x;
    while(z!=TATA[z])
    {
        aux=TATA[z];
        TATA[z]=y;
        z=aux;
    }
    return y;
}

int main(void)
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        ind[i]=i;
        scanf("%d%d%d",&X[i],&Y[i],&C[i]);
    }
    for(i=1;i<=n;i++)
        TATA[i]=i;
    sort(ind+1,ind+m+1,cmp);
    int nr=0;
    i=1;
    int t1,t2;
    while(nr<n&&i<=m)
    {
        j=ind[i];
        t1=tata(X[j]);
        t2=tata(Y[j]);
        if(t1!=t2)
        {
            cost+=C[j];
            TATA[t1] = t2;
            sol.push_back(j);
            nr++;
        }
        i++;
    }
    printf("%d\n%d\n",cost,nr);
    for(i=0;i<nr;i++)
        printf("%d %d\n",Y[sol[i]],X[sol[i]]);
    return 0;
}