#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
#define nmax 200005

using namespace std;

pair<int, pair<int,int> > a[nmax];
pair<int, int> rez[nmax];
int n, m, t[nmax];
int k = 0, c_min = 0;

bool cmp( pair<int,pair<int,int> > a, pair<int, pair<int,int> > b){

    return a.y.y < b.y.y;

}

void citeste(){

    scanf("%d%d", &n, &m);

    for(int i=1; i<=m; i++){
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        a[i] = make_pair(x, make_pair(y,c));
    }

    sort(a+1, a+m+1, cmp );

}

int radacina( int x ){

    int i = x;

    while(t[x]) x = t[x];
    while(i != x){
        int j = i;
        i = t[i];
        t[j] = x;
    }

    return x;

}

int uneste(int x, int y){

    x = radacina(x);
    y = radacina(y);

    t[x] = y;

}

void rezolva(){

    for(int i=1; i<=m; i++){
        int x = a[i].x;
        int y = a[i].y.x;
        int c = a[i].y.y;
        if ( radacina(x) == radacina(y) ) continue; // daca au aceeasi radacina;i`am unit deja;
        uneste(x,y);
        ++k;
        rez[k] = make_pair(x,y);
        c_min += c;
    }

}

void scrie(){

    printf("%d\n", c_min);
    printf("%d\n", n-1);
    for(int i=1; i<n; i++)
        printf("%d %d\n", rez[i].x, rez[i].y);

}

int main(){

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    citeste();
    rezolva();
    scrie();

    fclose(stdin);
    fclose(stdout);

    return 0;

}