#include <bits/stdc++.h>

#define DIM 200000

//#define int long long

using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

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

int n,m;
int x,y,c;
int sum = 0;

int len[DIM+5];
int t[DIM+5];

int k = 0;
struct info{
    int x;
    int y;
    int c;
}v[DIM+5],sol[DIM+5];

bool cmp(info x,info y){
    return x.c < y.c;
}

int getRoot(int x){

    if(t[x] == x){
        return x;
    }

    int rad = getRoot(t[x]);
    t[x] = rad;

    return rad;
}

void join(int x,int y){

    x = getRoot(x);
    y = getRoot(y);

    if(x != y){
        if(len[x] > len[y]){
            swap(x,y);
        }

        t[x] = y;
        if(len[x] == len[y]){
            len[y] ++;
        }
    }
}

signed main(){

    f>>n>>m;

    for(int i=1;i<=m;i++){
        f>>v[i].x>>v[i].y>>v[i].c;
    }

    sort(v+1,v+m+1,cmp);

    for(int i=1;i<=n;i++){
        t[i] = i;
        len[i] = 1;
    }

    for(int i=1;i<=m;i++){

        x = v[i].x;
        y = v[i].y;
        c = v[i].c;

        if(getRoot(x) == getRoot(y)){
            continue;
        }

        sum+=c;
        join(x,y);

        sol[++k] = v[i];
    }

    g<<sum<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++){
        g<<sol[i].x<<" "<<sol[i].y<<"\n";
    }

    return 0;
}