#include <bits/stdc++.h>
#define nax 102

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
int L[2*nax];
vector<int> ans;

struct muchie
{
    int x, y, cost;
}u[2*nax];

void init()
{
    int i;
    for(i = 1; i <= n; ++i)
        L[i] = i;
}

void Read()
{
    int x, y, cost, i = 0;
    f >> n >> m;
    while(f >> x >> y >> cost)
    {
        ++i;
        u[i].x = x;
        u[i].y = y;
        u[i].cost = cost;
    }
    sort(u+1, u+1+m, [&](muchie m1, muchie m2){return (m1.cost < m2.cost);});
}

int main()
{
    int i = 1, j, k = 0, x, y, cost = 0;
    Read();
    init();

//    g << "APM este format din muchiile: ";
    while(k < n - 1)
    {
        if(L[u[i].x] != L[u[i].y])
        {
            ++k;
            cost += u[i].cost;
            x = L[u[i].y];
            y = L[u[i].x];

            ans.push_back(u[i].x);
            ans.push_back(u[i].y);

            for(j = 1; j <= n; ++j)
                if(L[j] == x)
                    L[j] = y;
        }
        ++i;
    }
    ans.shrink_to_fit();
    g << cost << "\n" << (ans.size()>>1) << "\n";
    for(i = 0; i < ans.size(); i += 2)
        g << ans[i+1] << " " << ans[i] << "\n";
    return 0;
}