#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, t[101], rg[101], Total, k;

struct muchie{int x, y, c;}v[101];

pair < int, int> p[101];

int compare(muchie a, muchie b)
{
    return a.c < b.c;
}

void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort(v + 1, v + m + 1, compare);
    for(int i = 1; i <= n; i++)
    {
        t[i] = i;
        rg[i] = 1;
    }

}

int find(int nod)
{
    while(t[nod] != nod)
        nod = t[nod];
    return nod;
}

void unire(int x, int y)
{
    if(rg[x] < rg[y])
        t[x] = y;
    if(rg[y] < rg[x])
        t[y] = x;
    if(rg[x] == rg[y])
    {
        t[y] = x;
        rg[y]++;
     }
}

void kruskal()
{
    for(int i = 1; i <= m; i++)
    {
        if(find(v[i].x) != find(v[i].y))
        {
            unire(find(v[i].x), find(v[i].y));

            p[++k].first = v[i].x;
            p[k].second = v[i].y;
            Total += v[i].c;
        }
    }
}

void afisare()
{
    fout << Total << endl;
    fout << n - 1 << endl;
    for(int i = 1; i <= n; i++)
        fout << p[i].first <<" " << p[i].second << endl;
}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}