#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax = 205;
int T[nmax], n, m, cost, v[2 * nmax], k;
pair< int, pair<int, int> > E[2 * nmax];

int get_root(int node)
{
    if(T[node] > 0)
    {
        T[node] = get_root(T[node]);
        return T[node];
    }

    else
        return node;
}

int Join(int x, int y)
{
    int rx = get_root(x);
    int ry = get_root(y);

    if(rx == ry)
        return 0;

    if(T[rx] <= T[ry]){
        T[rx] += T[ry];
        T[ry] = rx;
    }

    else{
        T[ry] += T[rx];
        T[rx] = ry;
    }

    return 1;
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
        f >> E[i].second.first >> E[i].second.second >> E[i].first;

    sort(E + 1, E + m + 1);

    for(int i = 1; i <= n; i ++)
        T[i] = -1;

    for(int i = 1; i <= m; i ++)
    {
        int ok = Join(E[i].second.first, E[i].second.second);
        if(ok)
        {
            v[++ k] = i;
            cost += E[i].first;
        }
    }

    g << cost << '\n' << k << '\n';
    for(int i = 1; i <= k; i ++)
        g << E[i].second.second << " " << E[i].second.first << '\n';
    return 0;
}