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

using namespace std;

const int N = 200005;

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

vector<int> t;

int find(int x)
{
    if(t[x] == 0)
        return x;
    t[x] = find(t[x]);
    return t[x];
}

void unite(int x, int y)
{
    int tx = find(x);
    int ty = find(y);
    t[tx] = ty;
}

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

    // <cost, <x, y>>
    vector< pair<int, pair<int, int>> > muchii;
    muchii.resize(m);
    t.resize(n+1);
    for(int i = 0; i < m; i++)
    {
        int c, x, y;
        fin >> x >> y >> c;
        muchii[i] = {c, {x, y}};
    }

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

    int costArb = 0;
    vector<pair<int, int>> arbore;
    for(auto muchie : muchii)
    {
        int x = muchie.second.first;
        int y = muchie.second.second;
        int cost = muchie.first;

        if(find(x) != find(y))
        {
            arbore.push_back({x, y});
            costArb += cost;

            unite(x, y);
        }
    }
    
    fout << costArb << '\n' << arbore.size() << '\n';
    for(auto muchie : arbore)
        fout << muchie.first << ' ' << muchie.second << '\n';

    return 0;
}