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

using namespace std;

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

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

bool comp (edge a, edge b){
    return a.cost < b.cost;
}   

edge list[400005];
pair <int, int> sol[400005];
int father[200005], hight[200005];
int n, m, sum, idx = 1;

int find (int x){
    if (x == father[x])
        return x;
    int root = find (father[x]);
    father[x] = root;
    return root;
}

void unite (int x, int y, int cost){
    int setX, setY;

    setX = find(x);
    setY = find(y);

    if (setX != setY){
        sol[idx++] = {x, y};
        sum += cost;

        if (hight[setX] > hight[setY]){
            father[setY] = setX;
        }
        else if (hight[setX] < hight[setY]){
            father[setY] = setX;
        }
        else{
            father[setX] = setY;
            hight[setY]++;
        }
    }
}

int main (){
    in >> n >> m;
    for (int i=1; i<=m; ++i){
        in >> list[i].x >> list[i].y >> list[i].cost;
    }

    for (int i=1; i<=n; ++i)
        father[i] = i;

    sort (list + 1, list + m + 1, comp);

    for (int i=1; i<=m; ++i){
        unite (list[i].x, list[i].y, list[i].cost);
    }

    out << sum << '\n';
    out << idx-1 << '\n';
    for (int i=1; i<idx; ++i){
        out << sol[i].first << ' ' << sol[i].second << '\n';
    }

    return 0;
}