#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

#define INF 99999999
#define fth(x) (x>>1)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)+1)

using namespace std;

struct muchie
{
    int x, y, l;
}mch, mxmch, hp[400005];

int n, m, x, y, i, l, s, a[200005];

vector <muchie> v[200005];
vector <muchie>::iterator it;
vector <muchie> r;

void C(int x, int y)
{
    muchie aux=hp[x];
    hp[x]=hp[y];
    hp[y]=aux;
}

void UP(int x)
{
    if(x==1) return;
    int f=fth(x);
    if(hp[x].l<hp[f].l)
    {
        C(x, f);
        UP(f);
    }
}

void DOWN(int x)
{
    if(ls(x)>m) return;
    int son=ls(x);
    if(rs(x)<=m&&hp[rs(x)].l<hp[son].l) son++;
    if(hp[x].l>hp[son].l)
    {
        C(x, son);
        DOWN(son);
    }
}

void R(int x)
{
    muchie clr;
    clr.x=0;clr.y=0;clr.l=0;
    hp[x]=hp[m];
    hp[m]=clr;
    m--;
    DOWN(x);
    UP(x);
}

void I(muchie mch)
{
    m++;
    hp[m]=mch;
    UP(m);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &l);
        mch.x=x;mch.y=y;mch.l=l;
        v[x].push_back(mch);
        mch.y=x;mch.x=y;
        v[y].push_back(mch);
    }

    a[1]=1;
    s=0;
    m=0;
    for(it=v[1].begin();it!=v[1].end();it++)
    {
        mch=*it;
        I(mch);
    }
    for(i=1;i<=n-1;i++)
    {
        mch=hp[1];
        s+=mch.l;
        R(1);
        r.push_back(mch);
        a[mch.y]=1;
        for(it=v[mch.y].begin();it!=v[mch.y].end();it++)
            if(a[(*it).y]==0) I((*it));
        while(a[hp[1].x]==1&&a[hp[1].y]==1) R(1);
    }
    printf("%d\n%d\n", s, n-1);
    for(it=r.begin();it!=r.end();it++)
    {
        mch=*it;
        printf("%d %d\n", mch.x, mch.y);
    }
    return 0;
}