#include<fstream>

using namespace std;

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

struct muchie{

    int x, y, c;

} mu[400002];

int n, m, tt[200002], r[200005], sol = 0, id[200005], k = 0;

void citire(){

    fin>>n>>m;
    for(int i = 1; i <= m; i++)
        fin>>mu[i].x>>mu[i].y>>mu[i].c;

}

void sortare(){

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= m; j++)
            if(mu[i].c < mu[j].c)
                swap(mu[i], mu[j]);

}

int root(int x){

    while(tt[x] != x)
        x = tt[x];
    return x;

}

void unite(int x, int y){

    if(r[x] < r[y])
        tt[x] = y;
    if(r[x] > r[y])
        tt[y] = x;
    if(r[x] == r[y]){
        tt[y] = x;
        r[x]++;
    }

}

void rezolvare(){

    sortare();
    for(int i = 1; i <= n; i++)
        tt[i] = i;
    for(int i = 1; i <= n; i++)
        r[i] = root(i);
    for(int i = 1; i <= m; i++){
        int a = root(mu[i].x);
        int b = root(mu[i].y);
        if(a != b){
            unite(a, b);
            sol = sol + mu[i].c;
            id[++k] = i;
        }
    }

}

void afisare(){

    fout<<sol<<endl<<n-1<<endl;
    for(int i = 1; i <= k; ++i)
        fout<<mu[id[i]].x<<" "<<mu[id[i]].y<<endl;

}

int main(){

    citire();
    rezolvare();
    afisare();
    return 0;

}