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

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

struct muchie{
    int X, Y, cost;
};

vector <muchie> v;
vector <int> con, rasp;
int n, m, sol;

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

void cit(){
    con.push_back(0);
    muchie w;
    for (int  i=0;i<=m;++i){
        f>>w.X>>w.Y>>w.cost;
        v.push_back(w);
    }
    for (int i=1;i<=n;++i)
        con.push_back(i);
}

int main(){
    rasp.push_back(0);
    int i=0;
    f>>n>>m;
    cit();
    sort(v.begin(), v.end(), comp);
    for (int k=0;k<n-1&&i<m;++i){
        if (con[v[i].X]!=con[v[i].Y]){
            sol+=v[i].cost;
            k++;
            rasp.push_back(v[i].X);
            rasp.push_back(v[i].Y);
            //g<<v[i].X<<' ';
            //g<<v[i].Y<<'\n';
            for (int j=1;j<=n;++j)
                if (con[v[i].X]==con[j])
                    con[j]=con[v[i].Y];
        }
    }
    if(k==n-1)
    {
    g<<sol<<'\n'<<n-1<<'\n';
    for (int i=1;i<=2*n-2;i+=2){
        g<<rasp[i]<<' '<<rasp[i+1]<<'\n';
    }
    //g<<'\n';
    //for (int i=0;i<=m;++i)
        //g<<v[i].X<<' '<<v[i].Y<<' '<<v[i].cost<<'\n';
    }
    else g<<"0\0\n";
    g.close();
    return 0;
}