#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

int c_mod(int a, int b)
{
    if(a%b>=0)return a%b;
    return a%b+b;
}

int c_div(int a, int b)
{
    if(a%b>=0)return a/b;
    return a/b-1;
}

fstream f,g;

int hp[200002],hpl;

int val[200001],ort[200001],org[200001];

void swtch(int i,int j)
{
    org[hp[i]]=j;
    org[hp[j]]=i;

    int aux=hp[i];
    hp[i]=hp[j];
    hp[j]=aux;
}

int comp(int i,int j)
{
    if(val[i]<val[j])return 1;
    return 0;
}

void act(int i)
{
    while(i>1&&comp(hp[i],hp[i/2])==1)
    {
        swtch(i,i/2);
        i/=2;
    }
}

void del()
{
    int i=1;
    while(i*2<=hpl)
    {
        if(comp(hp[i*2],hp[i*2+1])==1||hpl==i*2)
        {
            swtch(i,i*2);
            i*=2;
        }
        else
        {
            swtch(i,i*2+1);
            i=i*2+1;
        }
    }
    swtch(i,hpl);
    act(i);
    hpl--;
}

struct lst
{
    int dst,cst;
    lst *urm;
}*p[200001],*u[200001];

int n,m,i,j,k,l,sol;

void add(int i,int j,int k)
{
    lst *n=new lst;
    n->dst=j;
    n->cst=k;
    n->urm=NULL;
    if(p[i]==NULL)p[i]=n;
    else u[i]->urm=n;
    u[i]=n;
}

int main()
{
    f.open("apm.in",ios_base::in);
    g.open("apm.out",ios_base::out);
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>l;
        add(j,k,l);
        add(k,j,l);
    }
    lst *ul;
    org[1]=-1;
    for(ul=p[1];ul!=NULL;ul=ul->urm)
    {
        hpl++;
        hp[hpl]=ul->dst;
        org[ul->dst]=hpl;
        ort[ul->dst]=1;
        val[ul->dst]=ul->cst;
        act(hpl);
    }
    while(hpl>1)
    {
        i=hp[1];
        del();
        sol+=val[i];
        org[i]=-1;
        for(ul=p[i];ul!=NULL;ul=ul->urm)if(org[ul->dst!=-1])
        {
            if(org[ul->dst]==0)
            {
                hpl++;
                hp[hpl]=ul->dst;
                org[ul->dst]=hpl;
                ort[ul->dst]=i;
                val[ul->dst]=ul->cst;
                act(hpl);
            }
            else if(ul->cst<val[ul->dst])
            {
                ort[ul->dst]=i;
                val[ul->dst]=ul->cst;
                act(org[ul->dst]);
            }
        }
    }
    g<<sol<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)g<<i<<' '<<ort[i]<<'\n';
}