#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;

struct muchie
{
    int x,y,c;
}mu[400001],ii;

int t[200001],n,m;

int cmp(const void *a, const void *b)
{
    return ((muchie*)a)->c - ((muchie*)b)->c;
}

void uneste(int i, int j)
{
    int x;
    for(x=1;x<=n;x++)
    {
        if(t[x]==i) t[x]=j;
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,j,k,cost=0,a,b;
    queue<muchie> r;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%d%d%d",&(mu[i].x),&(mu[i].y),&(mu[i].c));

    for(i=1;i<=n;i++)
        t[i]=i;

    qsort(mu,m,sizeof(muchie),cmp);

    for(k=0;k<m;k++)
    {
        if(t[mu[k].x]==t[mu[k].y]) continue;
        uneste(t[mu[k].x],t[mu[k].y]);
        cost+=mu[k].c;
        r.push(mu[k]);
    }
    printf("%d\n%d\n",cost,n-1);
    while(!r.empty())
    {
        ii=r.front();
        r.pop();
        printf("%d %d\n",ii.x,ii.y);

    }
    return 0;
}