#include <bits/stdc++.h>

using namespace std;
ofstream fout("apm.out");
ifstream fin("apm.in");

vector< pair<int, int> > G[200010];
vector< pair<int, int> > ans;
int d[200010];
int con[200010];
int h[200010];
int pos[200010];
int cost, n, m, x, y, c, l;

void apm(int node){
    for(auto next : G[node]){
        d[next.first] = min(d[next.first], next.second);
        if(d[next.first] == next.second) con[next.first] = node;
    }
}

void pushHeap(int x){
    while(x > 1 && d[h[x]] < d[h[x / 2]]){
        swap(h[x], h[x / 2]);
        swap(pos[h[x]], pos[h[x / 2]]);
        x /= 2;
    }
}

void addHeap(int i){
    h[++l] = i;
    pos[i] = l;

    pushHeap(l);
}

void popHeap(int x){
    while((x * 2 <= l && d[h[x]] > d[h[x * 2]]) || (x * 2 + 1 <= l && d[h[x]] > d[h[x * 2 + 1]])){
        if(d[h[x * 2]] <= d[h[x * 2 + 1]] || x * 2 + 1 > l){
            swap(h[x * 2], h[x]);
            swap(pos[h[x * 2]], pos[h[x]]);
            x = x * 2;
        }

        else{
            swap(h[x * 2 + 1], h[x]);
            swap(pos[h[x * 2 + 1]], pos[h[x]]);
            x = x * 2 + 1;
        }
    }
}

int root(){
    int x = h[1];
    swap(h[1], h[l]);
    swap(pos[h[1]], pos[h[l]]);
    l--;
    popHeap(1);

    return x;
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

    for(int i = 1; i <= n; i++){
        d[i] = 1000000000;
    }

    apm(1);

    for(int i = 2; i <= n; i++){
        addHeap(i);
    }

    for(int i = 1; i < n; i++){
        x = root();
        apm(x);
        ans.push_back({x, con[x]});
        pos[x] = 0;
        cost += d[x];
        for(auto node : G[x]){
            if(pos[node.first]) pushHeap(pos[node.first]);
        }
    }
    fout << cost << '\n' << ans.size() << '\n';
    for(auto sol : ans){
        fout << sol.first << ' ' << sol.second << '\n';
    }

    return 0;
}