#include <iostream>
#include <utility>
#include <vector>
#include <fstream>
#include <algorithm>
#include <list>

using namespace std;

int t[100000], h[100000];

void init(int n){
    for(int i = 1; i <= n ; i++){
        h[i] = 0;
        t[i] = i;
    }
}

int Find(int x){
    if(t[x] == x)
        return x;
    return Find(t[x]);
}

void Union(int x, int y){
    int a = Find(x);
    int b = Find(y);

    if(h[b] < h[b])
        t[a] = b;
    else if (h[b] > h[a]){
        t[b] = a;
    }
    else if (a != b){
        t[b] = a;
        h[a] += 1;
    }
    
}

int main()
{
    list <pair <int,int> > T;
    vector <pair <int, pair <int, int > > > E;
                //ponderea   capetele muchiei
    ifstream fin("apm.in");
    int n, m, i, x, y, p;
    fin >> n >> m;
    E.resize(m);
    
    for(i = 0; i < m; i++){
        fin >> x >> y >> p;
        E[i] = {p, {x,y}}; 
    }
    sort(E.begin(), E.end());

    // for( i = 0 ; i < m ; i++)
    //     cout << E[i].second.first << " " << E[i].second.second 
    //          << " " << E[i].first<<endl;
    
    int S = 0;
    int nr = 0;
    init(n);
    for( i = 0; i < m ; i++){
        x = E[i].second.first;
        y = E[i].second.second;
        p = E[i].first;

        if(Find(x) != Find(y)){
            T.push_back({x, y});
            S += p;
            Union(x, y);
            nr++;
        }
    }
    cout << S << endl;

    ofstream fout("apm.out");
    fout << S << endl;
    fout << nr << endl;
    
    for(auto it : T){
        cout << it.first << " " << it.second << endl;
        fout << it.first << " " << it.second << endl;
    }

    return 0;
}