#include <iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define nmax 200001
#define mmax 400001

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

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

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

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

void unire(int a, int b){
    int ga = grup[a], gb = grup[b];
    for(int i = 0; i < multimi[gb].size(); ++i){
        int x = multimi[gb][i];
        multimi[ga].push_back(x);
        grup[x] = grup[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);

    for(int i = 1; i <= n; ++i){
        grup[i] = i;
        multimi[i].push_back(i);
    }

    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(grup[a]!=grup[b]){
            unire(a, b);
            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;
}