#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, m, a, b, c, root[200005], cost;
vector<pair<int, pair<int, int>>> edges;
vector<pair<int, int>> sol;

int getRoot(int x)
{
    if ( x != root[x] )
        root[x] = getRoot(root[x]);
    return root[x];
}

void link(int x, int y)
{
    root[y] = x;
}

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

    for ( int i = 1; i <= m; i++ )
    {
        fin >> a >> b >> c;
        edges.push_back({ c, {a, b} });
    }
    for ( int i = 1; i <= n; i++ )
        root[i] = i;

    sort(edges.begin(), edges.end());

    for ( auto edge : edges )
    {
        int roota = getRoot(edge.second.first);
        int rootb = getRoot(edge.second.second);

        if ( roota != rootb )
        {
            link(roota, rootb);
            cost += edge.first;
            sol.push_back({ edge.second.first, edge.second.second });
        }
    }

    fout << cost << "\n" << sol.size() << "\n";

    for ( auto p : sol )
        fout << p.first << " " << p.second << "\n";

}