#include <bits/stdc++.h>
using namespace std;
#define NMAX 400005

struct vert{
    int left, right, cost;
}g[1*NMAX];

int tatic[NMAX], len[NMAX];

int getRoot(int node){
    if(tatic[node] == node){
        return node;
    }else getRoot(tatic[node]);
}

void uniteTrees(int l, int r){
    int x = getRoot(l),
        y = getRoot(r);
    if(len[x] > len[y]){
        swap(x,y);
    }
    tatic[x] = y;
    len[y] += len[x];
}

int main(void){
    /// kruskal's algorithm
    ofstream cout("apm.out");
    ifstream cin("apm.in");
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        len[i] = 1;
        tatic[i] = i;
    }
    for(int i = 1;i<=m;i++){
        int x, y, z;
        cin >> x >> y >> z;

        g[i].left = x;
        g[i].right = y;
        g[i].cost = z;
    }
    sort(g + 1, g + m + 1, [&](vert x, vert y) ->bool {
        return x.cost < y.cost;
    });
    vector<pair<int,int>> reconst;
    int ans = 0;
    for(int i = 1;i<=m;i++){
        ///cout << g[i].left << ' ' << g[i].right << ' ' << g[i].cost << '\n';
        /// avem mai multe cazuri , case 1 : unu dintre noduri este intr un arbore asadar il bagam si pe el doar daca nu face ciclu
        int xx = getRoot(g[i].left),
            yy = getRoot(g[i].right);
        if(xx != yy){
            /// nu sunt din acelasi union asa ca facem unul
            reconst.push_back({g[i].left, g[i].right});
            ans += g[i].cost;
            uniteTrees(g[i].left, g[i].right);
        }
    }
    cout << ans << '\n' << reconst.size() << '\n';
    for(auto [l,r] : reconst){
        cout << l << ' ' << r << '\n';
    }
    return 0;
}