#include <fstream>
#include <queue>
#include <functional>
#define NMAX 200001
#define MMAX 400001

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
int tata[NMAX];
int h[NMAX]; //inaltimea
struct muchie
{
    int x, y, c;
    friend bool operator> (muchie a, muchie b);
};
bool operator > (muchie a, muchie b)
{
    return a.c>b.c;
}
priority_queue <muchie, vector <muchie>, greater <muchie> > H;
vector <muchie> A; //apm
int cmin; //costul apm-ului
int Find(int x)
{
    int rad=x, y;
    while(tata[rad])
    {
        rad=tata[rad];
    }
    //compresia drumurilor
    if(rad!=x)
    {
        y=tata[x];
        while(y!=rad)
        {
            tata[x]=rad;
            x=y;
            y=tata[x];
        }
    }
    return rad;
}

void Union(int x, int y)
{
    int i, j;
    i=Find(x);
    j=Find(y);
    if(i!=j)
    {
        if(h[i]<h[j])
            tata[i]=j;
        else if(h[i]>h[j])
            tata[j]=i;
        else
        {
            tata[i]=j;
            h[j]++;
        }
    }
}
void citire();
void kruskal();
void afisare();

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}
void citire()
{
    int i;
    muchie aux;
    fin>>n>>m;
    for(i=0; i<m; ++i)
    {
        fin>>aux.x>>aux.y>>aux.c;
        H.push(aux);
    }
}
void kruskal()
{
    int i, j;
    muchie aux;
    while(A.size()<n-1)
    {
        aux=H.top();
        H.pop();
        i=Find(aux.x);
        j=Find(aux.y);
        if(i!=j)
        {
            A.push_back(aux);
            cmin+=aux.c;
            Union(i, j);
        }
    }
}
void afisare()
{
    int i;
    fout<<cmin<<'\n';
    fout<<n-1<<'\n';
    for(i=0; i<n-1; ++i)
        fout<<A[i].x<<' '<<A[i].y<<'\n';
}