#include <bits/stdc++.h>
using namespace std;

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

int n,m;
int tat[105];
int edges[10005];
int sum;
struct edge{
    int n1;
    int n2;
    int cost;
}v[10005];

bool compare(edge a, edge b) {
    return a.cost < b.cost;
}

int main()
{
    f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> v[i].n1 >> v[i].n2 >> v[i].cost;
    }
    sort(v+1,v+m+1,compare);
    for (int i=1;i<=m;i++) {
        if (tat[v[i].n1] == 0 && tat[v[i].n2] == 0) {
            edges[i] = 1;
            sum += v[i].cost;
            tat[v[i].n1] = v[i].n1; tat[v[i].n2] = v[i].n1;
        }
        else if (tat[v[i].n1] == 0 && tat[v[i].n2] != 0) {
            edges[i] = 1;
            sum += v[i].cost;
            tat[v[i].n1] = tat[v[i].n2];
        }
        else if (tat[v[i].n1] != 0 && tat[v[i].n2] == 0) {
            edges[i] = 1;
            sum += v[i].cost;
            tat[v[i].n2] = tat[v[i].n1];
        }
        else if (tat[v[i].n1] != tat[v[i].n2]) {
            int tata = tat[v[i].n2];
            for (int k=1;k<=n;k++) {
                    if (tat[k] == tata) {
                        tat[k] = tat[v[i].n1];
                    }
            }
            edges[i] = 1;
            sum += v[i].cost;
        }
    }
    g << sum << '\n' << n-1 << '\n';
    for (int i=1;i<=m;i++) {
        if (edges[i]==1) {
            g << v[i].n1 << " " << v[i].n2 << '\n';
        }
    }
    return 0;
}