#include <bits/stdc++.h>

using namespace std;

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

#if 1
#define cin fin
#define cout fout
#endif

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

#define MAX 200001
#define MOD % 666013
#define tt cout << "* ";
#define m1 {cout << "-1";return 0;}
#define da {cout << "DA";return 0;}
#define nu {cout << "NU";return 0;}
#define afisare(d) {for(auto x : d) cout << x << ' '; cout << '\n';}

vector<int> parent, rnk;
void make_set(int v){
    parent[v] = v;
    rnk[v] = 0;
}
int find_set(int v){
    if(v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a!=b){
        if(rnk[a] < rnk[b])
            swap(a, b);
        parent[b] = a;
        if(rnk[a] == rnk[b])
            rnk[a]++;
    }
}

struct edge{
    int u, v, c;
    bool operator<(const edge& o) const{
        return c < o.c;
    }
};

vector<edge> edges, res;
int n, m;

int main(){
    cin >> n >> m;
    parent.resize(n);
    rnk.resize(n);
    for(int i=0; i<n; ++i)
        make_set(i);

    while(m--){
        int u, v, c;
        cin >> u >> v >> c;
        edges.push_back({u-1, v-1, c});
    }

    sort(edges.begin(), edges.end());

    int cost = 0;
    for(edge e : edges){
        if(find_set(e.u) != find_set(e.v)){
            cost += e.c;
            res.push_back(e);
            union_sets(e.u, e.v);
        }
    }
    cout << cost << '\n' << res.size() << '\n';
    for(edge x : res)
        cout << x.v+1 << ' ' << x.u+1 << '\n';

    return 0;
}
///