#include<fstream>
#define nrmaxmuchii 400002
#define nrmaxvf 200002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int maxim(int x, int y)
{
    if(x>y) return x;
    else return y;
}

int minim(int x, int y)
{
    if(x<y) return x;
    else return y;
}
struct muchie
{
    int x,y,cost;
} g[nrmaxmuchii];
int A[nrmaxvf],c[nrmaxvf];
int n,m;

void citire()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>g[i].x>>g[i].y>>g[i].cost;
    for(i=1;i<=n;i++)
        c[i]=i;
    fin.close();

}

void sortare_muchii()
{
    muchie aux;
    int i,ok=0;
    while(!ok)
    {
        ok=1;
        for(i=1;i<=m-1;i++)
            if(g[i].cost>g[i+1].cost)
        {
            aux=g[i];
            g[i]=g[i+1];
            g[i+1]=aux;
            ok=0;
        }

    }
}

void afisare()
{
    int cost=0,i;
    for(i=1;i<n;i++)
        cost+=g[A[i]].cost;
    fout<<cost<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        fout<<g[A[i]].x<<' '<<g[A[i]].y<<'\n';
    fout.close();
}

int main()
{
    citire();
    sortare_muchii();
    int i,j,min,max,nrmsel=0;
    for(i=1;nrmsel<n-1;i++)
        if(c[g[i].x]!=c[g[i].y])
    {
        A[++nrmsel]=i;
        max=maxim(c[g[i].x],c[g[i].y]);
        min=minim(c[g[i].x],c[g[i].y]);
        for(j=1;j<=n;j++)
            if(c[j]==max) c[j]=min;
    }
    afisare();
    return 0;
}