#include <stdio.h>
#include <list>
#include <algorithm>
#include <utility>
using namespace std;

#define Nmax 200005
#define Mmax 400005

struct edge{
    int x, y, cost;
};

int n, m, sol;
int ind[Mmax], rang[Mmax], rad[Mmax];
edge edges[Mmax];
list < pair<int, int> > a;
list < pair<int, int> >::iterator it;

struct compare{
    bool operator() (int i, int j){return edges[i].cost < edges[j].cost;}
};
compare comp;

void read(){
    scanf("%i %i", &n, &m);
    for(register int i = 1; i <= m; ++i){
        scanf("%i %i %i", &edges[i].x, &edges[i].y, &edges[i].cost);
        ind[i] = i;
        rang[i] = 1;
        rad[i] = i;
    }
    fclose(stdin);
}

inline int find(int x){
    int r = x, aux;
    while(r != rad[r]) r = rad[r];

    while(x != r){
        aux = rad[x];
        rad[x] = r;
        x = aux;
    }

    return r;
}

inline void unite(int x, int y){
    if(rang[x] > rad[y])
        rad[y] = x;
        else
            rad[x] = y;
    if(rang[x] == rang[y]) ++rang[y];
}

void minim(){
    int rad1, rad2;
    sort(ind+1, ind+m+1, comp);

    for(register int i = 1; i <= m; ++i){
        rad1 = find(edges[ ind[i] ].x);
        rad2 = find(edges[ ind[i] ].y);

        if(rad1 != rad2){
            unite(rad1, rad2);
            sol += edges[ ind[i] ].cost;
            a.push_back( make_pair(edges[ ind[i] ].x, edges[ ind[i] ].y) );
        }
    }
}

void write(){
    printf("%i\n%i\n", sol, n-1);
    for(it = a.begin(); it != a.end(); ++it)
        printf("%i %i\n", it->first, it->second);
}

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

    read();
    minim();
    write();

    fclose(stdout);

    return 0;
}