#include <bits/stdc++.h>

using namespace std;

//ifstream f("file.in");
ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
vector<tuple<int, int, int> > G;
int t[200000];
vector<pair<int, int> > rez;
int costMin;

void read() {
    f >> n >> m;

    for(int i=0; i<m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        G.push_back(make_tuple(c, x, y));
    }
} 

int getRoot(int n) {
    if(t[n] == n)
        return n;
    t[n] = getRoot(t[n]);
    return t[n];
}

void apm() {

    for(int i=1; i<=n; i++) 
        t[i] = i;

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

    for(auto it : G) {
        
        int x, y, cost;

        tie(cost, x, y) = it;
        //cout<<cost<<" "<<x<<" "<< y<<endl;

        int rx = getRoot(x);
        int ry = getRoot(y);

        if(rx != ry) {
           // cout<<x<<" "<<y<<endl;
            rez.push_back(make_pair(x, y));
            costMin += cost;
            t[rx] = ry;
        }

    }
}

void print() {

    g << costMin << '\n' << rez.size() << '\n';

    for(int i=0; i<rez.size(); i++) 
        g << rez[i].first << " " << rez[i].second << '\n'; 
}

int main() {

    read();
    apm();
    print();
    return 0;
}