#include<iostream>
#include<fstream>

using namespace std;


ifstream f("apm.in");
ofstream out("apm.out");
int a[200000][200000],Q[200000],H[200000],n,m,r;
const int VMAX=500000;

void init_mc()
{
    int i,j;f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                a[i][j]=VMAX;
}

void citire_mc()
{
    int i,j,c;
    while(f>>i>>j>>c)
        {a[i][j]=c;
        a[j][i]=c;}
        f.close();
}

void init_Q()
{
    for(int i=1;i<=n;i++)
        if(i!=r)
            Q[i]=r;
}

int muchie()
{
    int i,j,min=VMAX;
    for(i=1;i<=n;i++)
        if(Q[i]!=0 && a[Q[i]][i]<min)
            {
            min=a[Q[i]][i];
            j=i;
            }
return j;
}

void actualizeaza_Q(int j)
{
    for(int i=1;i<=n;i++)
        if(Q[i]!=0 && a[i][Q[i]]>a[i][j])
            Q[i]=j;
}

void afisare()
{
    for(int i=1;i<=n;i++)
        if(H[i]!=0)
            out<<H[i]<<" "<<i<<"\n";
}

int main()
{
    int i=1,j,k=0,ct=0,t=0;
    init_mc();
    citire_mc();
    r=1;
    init_Q();
    while(k<n-1)
        {
        j=muchie();
        H[j]=Q[j];
        ct+=a[Q[j]][j];
        Q[j]=0;
        t++;
        actualizeaza_Q(j);
        k++;
        }
    out<<ct<<"\n"<<t<<"\n";
    afisare();

return 0;
}