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

void setIO(string name) {
    string input = name + ".in";
    string output = name + ".out";
    freopen(input.c_str(), "r", stdin);
    freopen(output.c_str(), "w", stdout);
}

const int N = 200000 + 5;

int n;
int m;
int par[N];
int sizes[N];
vector<tuple<int, int, int>> edges;

int get(int x) {
    return par[x] == x ? x : par[x] = get(par[x]);
}

void join(int a, int b) { 
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(sizes[a] > sizes[b]) swap(a, b);
    par[a] = b;
    sizes[b] += sizes[a];
}


int main(){
    setIO("apm");
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) par[i] = i, sizes[i] = 1;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        edges.emplace_back(make_tuple(w, u, v));
    }
    sort(edges.begin(), edges.end());
    vector<pair<int, int>> res;
    int sum = 0;
    for(auto e : edges) {
        int u, v, w;
        tie(w, u, v) = e;
        if(get(u) == get(v)) continue;
        join(u, v);
        sum += w;
        res.emplace_back(make_pair(u, v));
    }
    assert(res.size() + 1 == n);
    printf("%d\n", sum);
    printf("%d\n", (int)res.size());
    for(auto e : res) {
        printf("%d %d\n", e.first, e.second);
    }
    return 0;
}