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

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

vector<int>pr,nr;

int gaseste(int nod){

    if(pr[nod] == nod)
        return nod;

    return pr[nod] = gaseste(pr[nod]);
}

void uunion(int a,int b){

    a = gaseste(a);
    b = gaseste(b);

    if(a==b)
        return;

    if(nr[a] < nr[b])
        swap(a,b);

    nr[a] += nr[b];
    pr[b] = a;
}

struct arbore {

    int a,b,c;

    bool operator<(const arbore&other)const {
        return c < other.c;
    }
};


int main()
{

    int n,m;

    fin>>n>>m;

    pr.resize(n+1);
    nr.resize(n+1);

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

        pr[i]=i;
        nr[i]=1;
    }

    vector<arbore>mc,f;

    for(int i=1;i<=m;i++){
        int a,b,c;
        fin>>a>>b>>c;
        mc.push_back({a,b,c});
    }

    sort(mc.begin(),mc.end());

    int rez = 0;

    for(auto i : mc){

        if(gaseste(i.a) != gaseste(i.b)){
            rez+=i.c;
            uunion(i.a,i.b);
            f.push_back(i);
        }
    }

    fout<<rez<<'\n'<<n-1<<'\n';

    for(auto i : f)
        fout<<i.a<<" "<<i.b<<'\n';

    return 0;
}