#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 202000
#define INF (1<<30)-1
using namespace std;

int N, M, costMST, last, nrEdges, m;
vector< pair<int, int> > vertex[NMAX], MST;
int heap[NMAX], poz[NMAX], cost[NMAX], marcat[NMAX], pred[NMAX], nrh, aux;


void up(int p){
    while(p > 1 && cost[heap[p]] < cost[heap[p/2]]){
        swap(heap[p],heap[p / 2]);
        /*
        poz[heap[p]] = p;
        poz[heap[p/2]] = p/2;
        */
        swap(poz[heap[p]],poz[heap[p/2]]);
        p /= 2;
    }
}

void insert_heap(int x){
    heap[++nrh] = x;
    poz[x] = nrh;
    up(nrh);
}
void down(int p){
    int sl, sr, g = p;
    sl = p * 2; sr = p * 2 + 1;
    if(sl <= nrh && cost[heap[sl]] < cost[heap[g]]){
        g = sl;
    }
    if(sr <= nrh && cost[heap[sr]] < cost[heap[g]]){
        g = sr;
    }
    if(g != p){
        swap(heap[p],heap[g]);
         /*
        poz[heap[p]] = p;
        poz[heap[p/2]] = p/2;
        */
        swap(poz[heap[p]],poz[heap[g]]);
        down(g);
    }
}

int get_min(){
   m = heap[1];
   swap(heap[1],heap[nrh]);
   swap(poz[heap[1]],poz[heap[nrh]]);
   nrh--;
   //up(nrh);
   down(1);
   poz[m] = 0;
   return m;
}
int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &N, &M);
    int i, j, x, y, c;
    for(i = 1; i <= M; i++){
        scanf("%d%d%d", &x, &y, &c);
        vertex[x].push_back(make_pair(y, c));
        vertex[y].push_back(make_pair(x, c));
    }
    for(i = 1; i <= N; i++){
        cost[i] = INF;
    }
    cost[1] = 0;
    for(i = 1; i <= N; i++){
        insert_heap(i);
    }
    pred[1] = 0;
    for(i = 1; i <= N; i++){
        x = get_min();
        //printf("%d %d\n", x, cost[x]);
        marcat[x] = true;
        for(j = 0; j < vertex[x].size(); j++){
            y = vertex[x][j].first;
            c = vertex[x][j].second;
            if(c < cost[y] && !marcat[y]){
                cost[y] = c;
                pred[y] = x;
                up(poz[y]);
            }
        }
    }
    for(i = 1; i <= N; i++){
        costMST += cost[i];
    }
    printf("%d\n%d\n", costMST, N - 1);
    for(i = 1; i <= N; i++){
        if(pred[i]){
            printf("%d %d\n", i, pred[i]);
        }
    }
}