#include<fstream>
#include<algorithm>
#include <vector>
#define NMax 200006
#define MMax 400006
using namespace std;

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

int tata[NMax],rang[NMax];
muchie e[MMax];
int i,n,m;
int sol,ssol[NMax],edges;

bool Comp(muchie a, muchie b){
     return (a.cost<b.cost);
}

int radacina(int x){
    while(tata[x]!=x) x=tata[x];
    return x;
}

void Sudeaza(int x, int y){
     if(rang[x]>rang[y]) tata[y]=x;
     else tata[x]=y;
     if(rang[x]==rang[y]) rang[y]++;
}

int main()
{
    ifstream g("apm.in");
    ofstream f("apm.out");
    g>>n>>m;
    for(i=1;i<=m;i++){
        g>>e[i].x>>e[i].y>>e[i].cost;
    }

    sort(e+1,e+m+1,Comp);

    for(i=1;i<=n;i++){
        tata[i]=i;
        rang[i]=0;
    }

    for(i=1;i<=m;i++){
        int x = e[i].x;
        int y = e[i].y;
        int radx = radacina(x);
        int rady = radacina(y);

        if(radx!=rady){
            Sudeaza(radx,rady);
            sol += e[i].cost;
            ssol[++edges]=i;
        }
    }

    f<<sol<<"\n";
    f<<edges<<"\n";

    for(i=1;i<=edges;i++)
    f<<e[ssol[i]].x<<" "<<e[ssol[i]].y<<"\n";
}