#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct nod{
    int x , y , c;
    nod(int a,int b,int z){
        x=a;
        y=b;
        c=z;
    }
};

bool compFunc(nod a, nod b){
    if(a.c<b.c)return 1;return 0;
}

int sir[100001],rang[100001],k=0;

void combina(int x , int y) {
    if(rang[sir[x]]>rang[sir[y]])
        sir[y]=sir[x];
    else if(rang[sir[x]]<rang[sir[y]])
        sir[x]=sir[y];
    else {
        rang[sir[x]]++;
        sir[sir[y]]=sir[x];
    }
}

int cauta(int x , int y) {
    int done=0;
    k++;
    int i = x , j = y;
    while(sir[i]!=i)
        i=sir[i];
    while(sir[j]!=j)
        j=sir[j];
    if(i==j)done=1;
    int go;
    go=i;
    i=x;
    while(sir[i]!=go) {
        int aux=i;
        i=sir[i];
        sir[aux]=go;
    }
    go=j;
    i=y;
    while(sir[i]!=go) {
        int aux=i;
        i=sir[i];
        sir[aux]=go;
    }
    return done;
}

int main(){
    int n , m ,k=0,cap=0;
    vector<nod> noduri;
    fi>>n>>m;
    noduri.push_back(nod(0,0,-1001));
    for(int i=1;i<=m;i++)
    sir[i]=i;
    for(int i=0;i<m;i++){
        int x , y , c;
        fi>>x>>y>>c;
        noduri.push_back(nod(x,y,c));
    }
    sort(noduri.begin(),noduri.end(),compFunc);
    while(k++,k<=m){
        int x = noduri[k].x,y = noduri[k].y;
        if(!cauta(x,y)){
        combina(x,y);
        cap+=noduri[k].c;
        }else noduri[k].c=-1002;
    }
    fo<<cap<<'\n'<<n-1<<'\n';
    for(int i=1;i<=m;i++)
    if(noduri[i].c!=-1002)
    fo<<noduri[i].x<<' '<<noduri[i].y<<'\n';
}