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

struct muchie{
    int x, y, cost;
};

inline bool cmp(muchie a, muchie b){
    return a.cost<b.cost;
}
int N,M, dsj[200100], rang[200100]; muchie e[400100];
vector<muchie> sol;

int cauta(int x){
    int p = x,aux;
    while (p!=dsj[p])
        p=dsj[p];

    while (x!=dsj[x]){
        aux=dsj[x];
        dsj[x]=p;
        x=aux;
    }

    return p;
}

void uneste(int x, int y){
    if (rang[x]>rang[y])
        dsj[y]=x;
    else
        dsj[x]=y;

    if (rang[x]==rang[y])
        rang[y]++;
}

int main(){
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> N >> M;

    int i;
    for (i=1; i<=M; i++)
        in >> e[i].x >> e[i].y >> e[i].cost;
    sort(e+1,e+M+1,cmp);

    for (i=1; i<=N; i++){
        dsj[i]=i;
        rang[i]=1;
    }

    int sum=0;
    for (i=1; i<=M; i++){
        if (cauta(e[i].x)!=cauta(e[i].y)){
            sol.push_back(e[i]);
            sum+=e[i].cost;
            uneste(cauta(e[i].x),cauta(e[i].y));
        }
    }

    out << sum << "\n" << N-1 << "\n";
    for (i=0; i<sol.size(); i++)
        out << sol[i].x << " " << sol[i].y << "\n";
    return 0;
}