#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

struct vec
{
    int x,y,c;
}v[400001];

int n,m,c[200001],nrm,cost=0,a[400001],mn,mx;

bool cmp(vec i, vec j)
{
    if(i.c<j.c)return 1; else return 0;
}

void citire()
{
    int i;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
        fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    for(i=1;i<=n;i++)
        c[i]=i;
}

void solve()
{
    int i,j;
    nrm=0;
    for(i=1;nrm<n-1;i++)
        if(c[v[i].x]!=c[v[i].y])
    {
        cost+=v[i].c;
        a[++nrm]=i;
        if(c[v[i].x]<c[v[i].y])
        {
            mn=c[v[i].x];
            mx=c[v[i].y];
        } else
        {
            mn=c[v[i].y];
            mx=c[v[i].x];
        }
        for(j=1;j<=n;j++)
            if(c[j]==mx)c[j]=mn;
    }
}

void afisare()
{
    int i;
    fprintf(g,"%d\n",cost);
    fprintf(g,"%d\n",nrm);
    for(i=1;i<=nrm;i++)
        fprintf(g,"%d %d\n",v[a[i]].x,v[a[i]].y);
}

int main()
{
    citire();
    sort(v+1,v+1+m,cmp);
    solve();
    afisare();
    return 0;
}