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

ifstream in("apm.in");
ofstream out("apm.out");

const int MAX=400005;
struct info{
    int x;
    int y;
    int cost;
};

bool cmp(info a,info b){
    return a.cost<b.cost;
}

vector<int>T;
vector<int>SZ;

int root(int nod){
    if(T[nod]==nod)
        return nod;
    return T[nod]=root(T[nod]);
}

void unite(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx==ry)
        return;
    if(SZ[rx]<=SZ[ry]){
        SZ[ry]+=SZ[rx];
        T[rx]=ry;
    }else{
        SZ[rx]+=SZ[ry];
        T[ry]=rx;
    }
}

int main(){
    int n,m;
    in>>n>>m;
    SZ.resize(n+1);
    T.resize(n+1);
    vector<info>muchie(m+1);
    vector<pair<int,int>>rez;
    for(int i=1;i<=m;i++){
        in>>muchie[i].x>>muchie[i].y>>muchie[i].cost;
    }
    sort(muchie.begin()+1,muchie.end(),cmp);
    for(int i=1;i<=n;i++){
        T[i]=i;
        SZ[i]=1;
    }
    long long sum=0;
    for(int i=1;i<=m;i++){
        if(root(muchie[i].x)!=root(muchie[i].y)){
            unite(muchie[i].x,muchie[i].y);
            sum+=muchie[i].cost;
            rez.push_back({muchie[i].x,muchie[i].y});
        }
    }
    out<<sum<<"\n";
    out<<rez.size()<<"\n";
    for(auto nod:rez){
        out<<nod.first<<" "<<nod.second<<"\n";
    }
}