//Prim cu MinHeap
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#define NMax 101
#define inf 1000000000
#define min(a,b) (a<b?a:b)
using namespace std;

fstream fin("amp.in",ios::in);
fstream fout("amp.out",ios::out);

struct Nod{int ext; int cost;};
struct dimensiune{int nod; int cost;};

Nod *A[NMax];

int n,N,pre[NMax],x0;
int poz[NMax];
dimensiune dmin[NMax];


inline int left_son(int nod){return 2*nod;}
inline int right_son(int nod){return 2*nod+1;}
inline int father(int nod) {return nod/2;}

void Percolate(int K)
{
    //K - fiu
    int key=dmin[K].cost,tata=father(K);
    while(K>1&&dmin[tata].cost>key)
    {
        swap(poz[dmin[K].nod],poz[dmin[tata].nod]);
        swap(dmin[K],dmin[tata]);

        K=tata;
        tata=father(K);
    }
}

void sift(int N,int K)
{
    int son=0;
    do
    {
        son=0;
        if(left_son(K)<=N)
        {
            son=left_son(K);
            if(right_son(K)<=N&&dmin[left_son(K)].cost>dmin[right_son(K)].cost)
                son=right_son(K);
            if(dmin[son].cost>=dmin[K].cost)
                son=0;
        }
        if(son)
        {
            swap(poz[dmin[son].nod],poz[dmin[K].nod]);
            swap(dmin[son],dmin[K]);
            K=son;
        }
    }while(son);

}

void BuildHeap(int N)
{
    int i;
    for(i=N/2;i>=1;--i)
        sift(N,i);
}

int ExtractMin()//returneaza pozitia minimiului in heap
{
    swap(poz[dmin[N].nod],poz[dmin[1].nod]);
    swap(dmin[N],dmin[1]);

    poz[dmin[N].nod]=N;
    N--;

    sift(N,1);

    return N+1;
}


void Citire()
{
    int i,x,y,m;
    int cost;
    fin>>n>>m;
    N=n;
    x0=1;
    for(i=1;i<=n;i++)
    {
        A[i]=(Nod*)realloc(A[i],sizeof(Nod));
        A[i][0].ext=0;
        dmin[i].cost=inf;
        dmin[i].nod=i;
        poz[i]=i;

    }
    while(m--)
    {
        fin>>x>>y>>cost;
        A[x][0].ext++;
        A[x]=(Nod*)realloc(A[x],(A[x][0].ext+1)*sizeof(Nod));
        A[x][A[x][0].ext].ext=y;
        A[x][A[x][0].ext].cost=cost;

        A[y][0].ext++;
        A[y]=(Nod*)realloc(A[y],(A[y][0].ext+1)*sizeof(Nod));
        A[y][A[y][0].ext].ext=x;
        A[y][A[y][0].ext].cost=cost;

        if(x==x0) {dmin[y].cost=cost; pre[y]=x0;}
        else if(y==x0) {dmin[x].cost=cost; pre[x]=x0;}
    }
    dmin[x0].cost=-1001;
    pre[x0]=0;
    BuildHeap(N);

    ExtractMin();
}

void Update(int K)
{
    if(K>1&&dmin[father(K)].cost>dmin[K].cost)
        Percolate(K);
    else sift(K,N);
}

void PRIM()
{
    int i,pozMin,VfMin;
    int DMIN;
    while(N)
    {
        pozMin=ExtractMin();//am extras minimiul
        VfMin=dmin[pozMin].nod;
        DMIN=dmin[pozMin].cost;
        //actualizam
        for(i=1;i<=A[VfMin][0].ext;i++)
            if(poz[A[VfMin][i].ext]<=N&&A[VfMin][i].cost<dmin[poz[A[VfMin][i].ext]].cost)
            {
                pre[A[VfMin][i].ext]=VfMin;
                dmin[poz[A[VfMin][i].ext]].cost=A[VfMin][i].cost;
                Update(poz[A[VfMin][i].ext]);
            }
    }
}

void AfisareAMP()
{
    int i,j;
    int costAMP=0;
    dmin[poz[x0]].cost=inf;
    for(i=1;i<=n;i++)
        if(i!=x0)
        for(j=1;j<=A[i][0].ext;j++)
            if(A[i][j].ext==pre[i])
            {costAMP+=A[i][j].cost; break;}
    fout<<costAMP<<endl;
    fout<<n-1;
    for(i=1;i<=n;i++)
        if(i!=x0)
        fout<<endl<<pre[i]<<" "<<i;
}

int main()
{
    Citire();

    PRIM();

    AfisareAMP();

    return 0;
}