#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, cost, mincost;

vector<tuple<int, int, int>> t;
vector<pair<int, int>> ans;
vector<int> root, rang;

int comp(tuple<int, int, int> a, tuple<int, int, int> b)
{
    return ((get<2>(a)) < (get<2>(b)));
}

int getRoot(int node)
{
    while (root[node] != node)
        node = root[node];
    return node;
}

void Unite(int x, int y)
{
    if (rang[x] > rang[y])
        root[x] = y;
    else if (rang[x] > rang[y])
        root[y] = x;
    else
    {
        root[x] = y;
        rang[y]++;
    }
}

int main()
{
    fin >> n >> m;

    t.push_back(make_tuple(-1, -1, -1));
    root.push_back(-1);
    rang.push_back(-1);

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        t.push_back(make_tuple(x, y, cost));
    }

    sort(t.begin(), t.end(), comp);
    /*
    for (int i = 1; i <= m; i++)
    {
        int a = get<0>(t[i]);
        int b = get<1>(t[i]);
        int c = get<2>(t[i]);

        fout << a << " " << b << " " << c << '\n';
    }
*/
    for (int i = 1; i <= n; i++)
    {
        root.push_back(i);
        rang.push_back(i);
    }

    for (auto edge : t)
    {
        if (get<0>(edge) == -1 && get<1>(edge) == -1)
            continue;
        int x_root = getRoot(get<0>(edge));
        int y_root = getRoot(get<1>(edge));

        if (x_root != y_root)
        {
            Unite(x_root, y_root);
            mincost += (get<2>(edge));
            ans.push_back(make_pair((get<0>(edge)), (get<1>(edge))));
        }
    }

    fout << mincost << '\n'
         << ans.size() << '\n';

    for (auto it : ans)
        fout << it.second << " " << it.first << '\n';

    return 0;
}