#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

struct Muchie {
    int i;
    int j;
    int cost;
};

int Find(int nod);
void Union(int a, int b);
bool Cmp(Muchie a, Muchie b);

int n, m;
vector<int> t; 
vector<Muchie> x;
vector<pair<int,int>> rez;

int main() {
    ifstream reader("apm.in");
    ofstream writer("apm.out");

    reader >> n >> m;
    x.resize(m);
    t.resize(n+1);

    for(int i=0; i<m; i++)
        reader >> x[i].i >> x[i].j >> x[i].cost;

    sort(x.begin(), x.end(), Cmp);
    for(int i=1; i<=n; i++)
        t[i]=i;

    int suma=0;
    int nr=0;
    for(int i=0; i<m; i++) {
        int a=x[i].i;
        int b=x[i].j;
        if(Find(a) != Find(b)) {
            suma += x[i].cost;
            nr++;
            rez.push_back({a,b}); 
            Union(a,b);
        }
        if(nr == n-1)
            break;
    }

    writer << suma << endl;
    writer << rez.size() << endl;
    for(int i=0; i<(int)rez.size(); i++)
        writer << rez[i].first << " " << rez[i].second << endl;
    return 0;
}

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

void Union(int a, int b) {
    int radA = Find(a);
    int radB = Find(b);
    if(radA != radB)
        t[radB] = radA;
}

bool Cmp(Muchie a, Muchie b) {
    return a.cost < b.cost;
}