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

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

const int nmax = 100005;
int n,m;

vector<int> tata(nmax,-1);

struct muchie{
    int x,y,z;
    bool ok = 0;

    bool operator <(muchie i){
    return (i.z > this->z);
    }

}v[nmax];



int finde(int nod){
    if(tata[nod] < 0)return nod;

    else {

    int x = finde(tata[nod]);
    tata[nod] = x;
    return x;
    }

}

void Union(int x, int y){
    int tx = finde(x);
    int ty = finde(y);
    if(-tata[tx] < -tata[ty]){
        int t = tx;
        tx = ty;
        ty = t;
    }
    tata[tx] += tata[ty];
    tata[ty] = tx;
}

int main(){
    fin>>n>>m;

    for(int i = 1; i <= m; i++)
        fin>>v[i].x>>v[i].y>>v[i].z;

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

        int cost = 0, nr = 0;

        for(int i = 1; i <= m; i++){
            int x = finde(v[i].x), y = finde(v[i].y);

            if(x != y){
                cost += v[i].z;
                nr ++;
                v[i].ok = 1;
                Union(x,y);
            }
        }
        fout<<cost<<"\n"<<nr<<"\n";
        for(int i = 1; i <= m; i++)if(v[i].ok)fout<<v[i].x<<" "<<v[i].y<<"\n";

}