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

#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pii pair <int, int>

#define fr first 
#define sc second

using namespace std;

string filename = "apm";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

////////////////////////////////////////////////////////////


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 par[NMAX + 1];

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

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

    void Join(int a, int b){
        a = Find(a);
        b = Find(b);

        if(a == b){
            return;
        }

        par[a] = b;
    }
}

void solve(){
    int n, m;
    fin >> n >> m;

    DSU::init(n);

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

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

    int cost = 0;
    vt <pii> apm;
    for(int i = 1; i <= m; i++){
        if(DSU::Find(edges[i].a) != DSU::Find(edges[i].b)){
            cost += edges[i].c;
            DSU::Join(edges[i].a, edges[i].b);
            apm.pb({edges[i].a, edges[i].b});
        }
    }

    fout << cost << '\n';
    fout << n - 1 << '\n';
    for(pii x : apm){
        fout << x.fr << ' ' << x.sc << '\n';
    }
}

int main(){

    int T;
    //fin >> T;

    T = 1;

    while(T--){
        solve();
    }

    return 0;
}