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

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

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

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

int main()
{
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);
    in>>n>>m;
    for(int i = 0; i < m; ++i){
        int a, b, c; in>>a>>b>>c;
        muchii.push_back(make_pair(c, make_pair(a, b)));
    }
    sort(muchii.begin(), muchii.end());

    int sum = 0, nr_muchii = 0;
    for(int i = 0; i < muchii.size(); ++i){
        if(nr_muchii == n-1)
            break;
        int a = muchii[i].second.first, b = muchii[i].second.second;
        int ra = root(a), rb = root(b);
        if( ra != rb ){

            tata[rb] = ra;
            sum += muchii[i].first;
            ++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;
}