#include <bits/stdc++.h>
#define inf 2147483647

using namespace std;

vector< pair<int, short> > L[200005];

int caut(int where, int who) {
    for(int i = 0; i < L[where].size(); i ++) {
        if(L[where][i].first == who)
            return i;
    }
    return -1;
}

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

    int n, m, x, y, cost;
    f >> n >> m;
    for(int i = 1; i <= m; i ++) {
        f >> x >> y;
        f >> cost;
        L[x].push_back(make_pair(y, cost));
        L[y].push_back(make_pair(x, cost));
    }

    bool s[200005];
    int tata[200005];
    int c[200005];

    for(int i = 1; i <= n; i ++) {
        tata[i] = 1;
        s[i] = false;
        int poz = caut(1, i);
        if(poz != -1) {
            c[i] = L[i][poz].second;
        }
        else c[i] = inf;
    }
    s[1] = true;

    for(int i = 1; i < n; i ++) {
        int mn = inf;
        int poz = 1;
        for(int i = 1; i <= n; i ++) {
            if(!s[i] && mn > c[i]) {
                mn = c[i];
                poz = i;
            }
        }

        s[poz] = true;
        for(int i = 1; i <= n; i ++) {
            if(!s[i]) {
                int pozCaut = caut(poz, i);
                if(pozCaut != -1) {
                    if(c[i] > L[poz][pozCaut].second) {
                        tata[i] = poz;
                        c[i] = L[poz][pozCaut].second;
                    }
                }
            }
        }
    }

    cost = 0;
    for(int i = 2; i <= n; i ++) {
        int poz = caut(tata[i], i);
        if(poz != -1)
            cost += L[tata[i]][poz].second;
    }
    g << cost << "\n" << n - 1 << "\n";
    for(int i = 2; i <= n; i ++) {
        g << tata[i] << " " << i << "\n";
    }
    return 0;
}