#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
unsigned long n,m,A[200001];
long cost=0;
vector<unsigned long>T;
struct muchii
{
    unsigned long n1,n2;
    int c;
}v[400001],aux,pivot;
void citire()
{
    ifstream f("apm.in");
    f>>n>>m;
    for (unsigned long i=1;i<=m;i++)
    {
        f>>v[i].n1>>v[i].n2>>v[i].c;
        if (i<=n) T.push_back(i);
    }
}
void sortare(int left, int right)
{
    int i = left, j = right;
    pivot = v[(left + right) / 2];
    while (i <= j)
    {
        while (v[i].c < pivot.c)
            i++;
        while (v[j].c > pivot.c)
            j--;
        if (i <= j)
        {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            i++;
            j--;
        }
    };
    if (left < j)
        sortare(left, j);
    if (i < right)
        sortare(i, right);
}
void kruskal()
{
    unsigned long i,j,minim,maxim,nr_sel=0;
    for (i=1;nr_sel<n-1;i++)
        if (T[v[i].n1]!=T[v[i].n2])
        {
            A[++nr_sel]=i;
            cost+=v[i].c;
            if (T[v[i].n1]<T[v[i].n2])
            {
                minim=T[v[i].n1];
                maxim=T[v[i].n2];
            }
            else
            {
                minim=T[v[i].n2];
                maxim=T[v[i].n1];
            }
            for (j=1;j<=n;j++)
                if (T[j]==maxim) T[j]=minim;
        }
}
void afisare()
{
    ofstream f("apm.out");
    f<<cost<<"\n"<<n-1<<"\n";
    for (int i=1;i<=n-1;i++)
        f<<v[A[i]].n1<<" "<<v[A[i]].n2<<"\n";
}
int main()
{
    citire();
    sortare(1,m);
    kruskal();
    afisare();
    return 0;
}