#include<fstream>
#include<vector>
#include<algorithm>
#define nmax 200001

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

struct mm{
    int k, a, b;
};

int n, m, tata[nmax];
vector<mm> muchii;
vector<int>rez;

bool compare(mm a, mm b){
    return (a.k < b.k);
}

int root(int a){
    if(tata[a] == 0) return a;
    root(tata[a]);
}

int main()
{
    in>>n>>m;
    for(int i = 0; i < m; ++i){
        mm x;
        in>>x.a>>x.b>>x.k;
        muchii.push_back(x);
    }
    sort(muchii.begin(), muchii.end(), compare);

    int sum = 0, nr_muchii = 0;
    for(int i = 0; i < muchii.size(); ++i){
        if(nr_muchii == n-1)
            break;
        int a = muchii[i].a, b = muchii[i].b;
        if( root(a) != root(b)){
            tata[root(b)] = root(a);
            sum += muchii[i].k;
            ++nr_muchii;
            rez.push_back(a);
            rez.push_back(b);
        }
    }

    out<<sum<<'\n'<<nr_muchii<<'\n';
    for(int i = 0; i < rez.size(); i+=2)
        out << rez[i] << ' ' << rez[i+1] << '\n';

    in.close();
    out.close();
    return 0;
}