#include <fstream>
#include <bits/stdc++.h>

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

struct Edge{
    int x, y, cost;
};

bool cmp(Edge e1, Edge e2){
    return e1.cost < e2.cost;
}

vector <int> root;
vector <Edge> edges;

int get_root(int node){
    if (root[node] == node){
        return node;
    }
    root[node] = get_root(root[node]);
    return root[node];
}

void group (int r1, int r2){
    root[r1] = r2;
}


int main(){
    int n, m;
    int cost = 0;

    f >> n >> m;
    int x, y ,c;

    for(int i = 0 ; i <= n; i ++)
        root.push_back(i);
    for(int i = 0; i < m; i ++){
        f >> x >> y >> c;
        Edge e;
        e.x = x;
        e.y = y;
        e.cost = c;
        edges.push_back(e);
    }

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

    vector <Edge> sol;
    for (auto edge : edges){
        int r1 = get_root(edge.x);
        int r2 = get_root(edge.y);
        if (r1 != r2){
            cost += edge.cost;
            sol.push_back(edge);
            group(r1, r2);
        }
    }

    g << cost << '\n';
    g << sol.size() << '\n';
    for (auto edge : sol){
        g << edge.x << " " << edge.y << '\n';
    }


}