#include <fstream>
#include <algorithm>

using namespace std;

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

int cnt,S;

struct muchie
{
    int i,j,cost;
};

int n, m, t[200001];

muchie x[200001];
muchie v[200001];

int radacina(int x)
{
    if(x==t[x])
    {
        return x;
    }
    else return radacina(t[x]);
}

int compara(muchie x, muchie y)
{
    return x.cost < y.cost;
}

void verif(int x, int y)
{
    t[x]=t[y];
}

void kruskal()
{
    int ai,aj;
    for(int i = 1 ; i <= m  ; i ++)
    {
        ai = radacina(x[i].i);
        aj = radacina(x[i].j);
        if(ai!=aj)
        {
            S += x[i].cost;
            v[++cnt]=x[i];
            verif(ai,aj);
        }
    }
}

int main()
{
    fin >> n >> m;

    for(int i = 1 ; i <= m ; i++)
        {fin >> x[i].i >> x[i].j >> x[i].cost;}

    sort(x+1, x+m+1, compara);
    for(int i =1 ; i <= n ; ++i)
        t[i] = i;
    kruskal();
    fout << S << "\n"<<n-1<<'\n';
    for(int i = 1 ; i < n ; ++i)
        fout << x[i].i << " " << x[i].j << "\n";
    return 0;
}