#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<int>vectorTati;
vector<int>vectorInaltimi;
int reprezentant(int a) {
    if (vectorTati[a]==0) return a;
    else {
        vectorTati[a] = reprezentant(vectorTati[a]);
        return vectorTati[a];
    }
}
void reunire(int x, int y) {
    x=reprezentant(x);
    y=reprezentant(y);
    if (vectorInaltimi[x]<vectorInaltimi[y]) {
        vectorTati[x]=y;
    }
    else if (vectorInaltimi[x]==vectorInaltimi[y]) {
        vectorTati[x]=y;
        vectorInaltimi[y]++;
    }
    else vectorTati[y]=x;
}
vector<vector<int>> kruskal (vector<vector<int>>muchii, int nrNoduri) {
    vectorTati.assign(nrNoduri+1,0);
    vectorInaltimi.assign(nrNoduri+1,0);
    sort(muchii.begin(),muchii.end());
    vector<vector<int>> rezultat;
    for (auto m : muchii) {
        if (reprezentant(m[1])!=reprezentant(m[2])) {
            reunire(m[1],m[2]);
            rezultat.push_back(m);
            if (rezultat.size() >= nrNoduri - 1) break;
        }
    }
    return rezultat;
}
int main(){
    int n, m;
    fin>>n>>m;
    vector<vector<int>>muchii;
    for (int i=1;i<=m;i++) {
        int a, b,c;
        fin>>a>>b>>c;
        muchii.push_back({c,a,b});
    }
    vector<vector<int>>rez;
    rez = kruskal(muchii,n);
    int suma=0;
    for (auto muchie : rez) {
        suma+=muchie[0];
    }
    fout<<suma<<endl<<rez.size()<<endl;
    for (auto muchie : rez) {
        fout<<muchie[1]<<" "<<muchie[2]<<endl;
    }
    return 0;
}