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

using namespace std;

#define pii pair <int, int>

string filename = "apm";

#ifdef LOCAL
    ifstream fin("input.in");
    ofstream fout("output.out");
#else
    ifstream fin(filename + ".in");
    ofstream fout(filename + ".out");
#endif

const int NMAX = 2e5;

struct Edge{
    int a, b, c;
}edges[2 * NMAX + 1];

bool cmp(Edge x, Edge y){
    return x.c < y.c;
}

namespace DSU{
    int parent[NMAX + 1];

    void init(int n){
        for(int i = 1; i <= n; i++){
            parent[i] = i;
        }
    }

    int Find(int x){
        if(x == parent[x]){
            return x;
        }
        return parent[x] = Find(parent[x]);
    }

    void Join(int a, int b){
        a = Find(a);
        b = Find(b);
        parent[a] = b;
    }
}

int main(){

    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        int a, b, c;
        fin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    sort(edges + 1, edges + m + 1, cmp);

    DSU::init(n);

    int ans = 0;
    vector <pii> conf;
    for(int i = 1; i <= m; i++){
        if(DSU::Find(edges[i].a) != DSU::Find(edges[i].b)){
            ans += edges[i].c;
            DSU::Join(edges[i].a, edges[i].b);
            conf.push_back({edges[i].a, edges[i].b});
        }
    }

    fout << ans << '\n';

    fout << (int)conf.size() << '\n';
    for(pii x : conf){
        fout << x.first << ' ' << x.second << '\n';
    }

    return 0;
}