#include <bits/stdc++.h>
#define DIM 200001
#define int long long

using namespace std;

ifstream fin("apm.in");

ofstream fout("apm.out");

struct edge{

    int i, j, cost;

};

static inline bool cmp(const edge &a, const edge &b){\

    return (a.cost < b.cost);

}

edge v[2 * DIM];

int father[DIM], taken[DIM];

int n, m, i, cost;

int get_root(int node){

    if(!father[node])

        return node;

    int x = get_root(father[node]);

    father[node] = x;

    return x;

}

void join(int a, int b){

    father[a] = b;

}

int32_t main(){

    fin >> n >> m;

    for(i=1;i<=m;i++){

        fin >> v[i].i >> v[i].j >> v[i].cost;

    }

    std :: sort(v + 1, v + m + 1, cmp);

    for(i=1;i<=m;i++){

        if(get_root(v[i].i) != get_root(v[i].j)){

            join(get_root(v[i].i), get_root(v[i].j));

            cost += v[i].cost;

            taken[i] = 1;

        }

    }

    fout << cost << "\n" << n - 1 << "\n";

    for(i=1;i<=m;i++)

        if(taken[i])

            fout << v[i].i << " " << v[i].j << "\n";

}