#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

long N,M,t[200001];
struct muchie
{
    int x,y,cost;
}m[200001];

muchie aux,linii[400001];

void citire()
{
    int i,j;
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>m[i].x>>m[i].y>>m[i].cost;
    }
    for(i=1;i<=N;i++)
    {
        t[i]=i;
    }
}


int main()
{int i,j;
citire();
for(i=1;i<M;i++)
{
    for(j=i+1;j<=M;j++)
    {
        if(m[i].cost>m[j].cost)
        {
            aux=m[i];
            m[i]=m[j];
            m[j]=aux;
        }
    }
}
int k=0,suma=0,p=1;
while(k<N-1)
{
    if(t[m[p].x]!=t[m[p].y])
    {
        k++;
        suma=suma+m[p].cost;
        linii[k].x=m[p].x;
        linii[k].y=m[p].y;
        linii[k].cost=m[p].cost;
        int v=t[m[p].y];
        int b=t[m[p].x];
        for(i=1;i<=N;i++)
        {
            if(t[i]==v)
            {
                t[i]=b;
            }
        }


    }
    p++;
}
fout<<suma<<endl;
fout<<k<<endl;
for(i=1;i<p;i++)
{
    fout<<linii[i].y<<" "<<linii[i].x<<endl;
}

return 0;
}