//#include <iostream>
#include <stdio.h>
#include <vector>
#define nmax 200001
#define inf 999999
using namespace std;
FILE *f=fopen("apm.in","r"),*g=fopen("apm.out","w");
struct per{
long dest,c;};
long heap[nmax],poz[nmax],start,lgheap,p[nmax],v[nmax];
vector <per> l[nmax],r;
void swaps(long p1, long p2)
{
    long aux;
    poz[heap[p1]]=p2;
    poz[heap[p2]]=p1;
    aux=heap[p1];
    heap[p1]=heap[p2];
    heap[p2]=aux;
}
void urca(long p)
{
    while(p/2>0&&v[heap[p/2]]>v[heap[p]])
    {
        swaps(p,p/2);
        p=p/2;
    }
}
void coboara(long p)
{
    long ok,mini=inf,poz;
    do{
        ok=0;
        mini=inf;
        if(p*2<=lgheap&&v[heap[p*2]]<v[heap[p]])
        {
            ok=1;
            if(v[heap[p*2]]<mini)
            {
                poz=p*2;
                mini=v[heap[p*2]];
            }
        }
        if(p*2+1<=lgheap&&v[heap[p*2+1]]<v[heap[p]])
        {
            ok=1;
            if(v[heap[p*2+1]]<mini)
            {
                poz=p*2+1;
                mini=v[heap[p*2+1]];
            }
        }
        if(ok)
            {swaps(p,poz);
            p=poz;}
    }while(ok);
}
void introd_in_arb(long k)
{
    long i,j;
    for(i=0;i<l[k].size();i++)
        if(poz[l[k][i].dest]>0||lgheap==0)
    {
        if(v[l[k][i].dest]>l[k][i].c)
        {v[l[k][i].dest]=l[k][i].c;
        p[l[k][i].dest]=k;
        urca(poz[l[k][i].dest]);
        }
    }
}
int main()
{
    long i,j,m,x,y,n;
    long long sum=0;
    per aux;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&x,&aux.dest,&aux.c);
        l[x].push_back(aux);
        y=aux.dest;
        aux.dest=x;
        l[y].push_back(aux);
    }
    fclose(f);
    for(i=2;i<=n;i++)
        v[i]=inf;
    v[1]=0;
        start=1;
    introd_in_arb(start);
    for(i=2;i<=n;i++)
    {
        lgheap++;
        poz[i]=lgheap;
        heap[lgheap]=i;
        urca(lgheap);
    }
    for(i=1;i<n;i++)
    {
        start=heap[1];
        swaps(1,lgheap);
        poz[start]=-1;
        lgheap--;
        coboara(1);
        introd_in_arb(start);
        sum+=v[start];
        aux.c=start;
        aux.dest=p[start];
        r.push_back(aux);
    }
    fprintf(g,"%ld\n",sum);
    fprintf(g,"%ld\n",n-1);
    for(i=0;i<r.size();i++)
        fprintf(g,"%ld %ld\n",r[i].c,r[i].dest);
        fclose(g);
    return 0;
}