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

ifstream fin("f.in");
ofstream fout("f.out");
const int maxn = 2e5 + 2;
const int maxm = 4e5 + 2;
const int mod = 666013;
#define ll  long long

int t[maxn + 2], rang[maxn + 2];
int n, m, ans;
vector<pair<int, int>> edges;
struct edge{
    int st, dr, cost;
}a[maxn + 2];
void read() {
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        fin >> a[i].st >> a[i].dr >> a[i].cost;
    }
}
int get_root(int i){
    if(t[i] == i)
        return i;
    return t[i] = get_root(t[i]);
}
void unite(int i, int j){
    if(rang[i] > rang[j])
        t[j] = i;
    else{
        t[i] = j;
        if(rang[i] == rang[j])
            rang[i]++;
    }
}
void init(){
    for(int i = 1; i <= n; ++i)
        rang[i] = 1, t[i] = i;
}
bool cmp(edge x, edge y){
    return x.cost < y.cost;
}
void solve(){
    sort(a + 1, a + m + 1, cmp);
    for(int i = 1; i <= m; ++i){
        int r1 = get_root(a[i].st);
        int r2 = get_root(a[i].dr);
        if(r1 != r2){
            unite(r1, r2);
            ans += a[i].cost;
            edges.push_back({a[i].st, a[i].dr});
        }


    }
}
void display(){
    fout << ans << "\n" << edges.size() << "\n";
    for(auto x : edges){
        fout << x.first << " " << x.second << "\n";
    }
}
int main(){
    read();
    init();
    solve();
    display();
    return 0;

}
/*


*/