#include<stdio.h>
#include<vector>
#include<ctype.h>
using namespace std;

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

typedef vector<pair<int,int> >::iterator it;

#define MaxN 200100
#define MaxS 30
#define mij ((li+ls)>>1)
#define fs (poz<<1)
#define fd ((poz<<1)+1)
#define INF (1<<29)

int N,M,Sol;
int D[MaxN],viz[MaxN],muchie[MaxN];
int AINT[MaxN*3],POZAINT[MaxN*3];
char S[MaxS];
vector<pair<int,int> > A[MaxN];

void citire(void)
{
    int a,b,c,j,semn;

    fscanf(f,"%d %d\n",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fgets(S,sizeof(S),f);
        for(j=0,a=0;isdigit(S[j]);a = a*10+S[j++]-'0');j++;
        for(b=0;isdigit(S[j]);b=b*10+S[j++]-'0');j++;
        if(S[j] == '-')
            semn = -1, ++j;
        else
            semn = 1;
        for(c=0;isdigit(S[j]);c=c*10+S[j++]-'0');
        c *= semn;
        A[a].push_back(make_pair(b,c));
        A[b].push_back(make_pair(a,c));
    }
}

inline void insert(int li,int ls,int poz,int val,int pozVal)
{
    if(li == ls)
    {
        AINT[poz] = val;
        POZAINT[poz] = li;
        return ;
    }

    if(li <= pozVal && pozVal <= mij)
        insert(li,mij,fs,val,pozVal);
    else
        insert(mij+1,ls,fd,val,pozVal);

    if(AINT[fs] < AINT[fd])
        AINT[poz] = AINT[fs],POZAINT[poz] = POZAINT[fs];
    else
        AINT[poz] = AINT[fd],POZAINT[poz] = POZAINT[fd];
}

void initializare(void)
{
    for(int i=1;i<MaxN*3;i++)
        AINT[i] = INF;
    for(int i=2;i<=N;i++)
        D[i] = INF;
}

void Prim(void)
{
    insert(1,N,1,0,1);

    for(int i=1;i<=N;i++)
    {
        Sol += AINT[1];

        int poz = POZAINT[1];
        viz[poz] = 1;
        for(it j=A[poz].begin();j<A[poz].end();j++)
            if(!viz[j->first] && D[j->first] > j->second)
            {
                D[j->first] = j->second;
                muchie[j->first] = poz;
                insert(1,N,1,j->second,j->first);
            }

        insert(1,N,1,INF+1,poz);
    }
}

int main()
{
    citire();
    initializare();
    Prim();

    fprintf(g,"%d\n%d\n",Sol,N-1);
    for(int i=2;i<=N;i++)
        fprintf(g,"%d %d\n",muchie[i],i);
}