#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

pair<int,pair<int, int> > M[400001];
int d[200001], sol[200001];
int n, m;

int get_root(int node)
{
    while(d[node] > 0)
        node = d[node];
    return node;
}

int main()
{
    int i, x, y, cost, total_cost = 0, gasit = 0;
    f >> n >> m;
    for(i = 0; i < n; i++)
        d[i] = -1;
    for(i = 0; i < m; i++){
        f >> x >> y >> cost;
        M[i].first = cost;
        M[i].second = std::make_pair(x, y);
    }
    sort(M, M + m);

    for(i = 0; i < m && gasit != n; i++){
        int node_1 = M[i].second.first, node_2 = M[i].second.second;
        int r1 = get_root(node_1), r2 = get_root(node_2);
        cost = M[i].first;

        if(r1 != r2){
            if(d[r1] < d[r2]){
                d[r1] += d[r2];
                d[r2] = r1;
            }
            else{
                d[r2] += d[r1];
                d[r1] = r2;
            }

        sol[gasit++] = i;
        total_cost += cost;
        }
    }

    g << total_cost << endl << gasit << endl;
    for(i = 0; i < gasit; i++)
        g << M[sol[i]].second.second << " " << M[sol[i]].second.first << endl;

    return 0;
}