#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 200003

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

int n, m;

struct truple
{
    int a, b, c;
    bool ex;
};

truple v[MAX * 2];
int tata[MAX];
bool comp(truple a, truple b)
{
    return a.c < b.c;
}
int findTata(int x)
{
    if(tata[x] == x)
        return x;

    int rez = findTata(tata[x]);
    tata[x] = rez;
    return rez;
}
int main()
{
    int costTotal = 0;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>v[i].a>>v[i].b>>v[i].c;

    sort(v+1, v+m+1, comp);
    for(int i=1; i<=n-1; i++)
        tata[i] = i;

    for(int i=1; i<=m; i++)
    {
        int ta, tb;
        ta = findTata(v[i].a);
        tb = findTata(v[i].b);
        if(ta != tb)
        {
            tata[ta] = tb;
            v[i].ex = 1;
            costTotal += v[i].c;
        }
    }
    fout<<costTotal<<'\n'<<n-1<<'\n';
    for(int i=1; i<=m; i++)
        if(v[i].ex)
            fout<<v[i].a<<' '<<v[i].b<<'\n';
    return 0;
}