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

using namespace std;

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

int t[200001],n,m;
list<int> ml[200001];
list<int>::const_iterator iter,fin;

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;
    }
*/
    for(iter=ml[i].begin(),fin=ml[i].end();iter!=fin;iter++)
        t[*iter]=j;
    ml[j].splice(ml[j].end(),ml[i]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,j,k,cost=0,a,b,nrm=0,nrmmax;
    queue<muchie> r;
    scanf("%d%d",&n,&m);
    nrmmax=n-1;
    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;
        ml[i].push_back(i);
    }

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

    for(k=0;k<m&&nrm<nrmmax;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]);
        nrm++;
    }
    printf("%d\n%d\n",cost,nrmmax);
    while(!r.empty())
    {
        ii=r.front();
        r.pop();
        printf("%d %d\n",ii.x,ii.y);

    }
    return 0;
}