#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 2e5, M = 4e5;
const int INF = 1 << 30;

struct element{
    int node, cost, next;
}v[M + 1];

int lst[N + 1], n, m, nr, nh;
int d[N + 1], h[N + 1], pos[N + 1], ant[N + 1];
bool in_apm[N + 1];

void add(int x, int y, int c){
    v[++nr].node = y;
    v[nr].cost = c;
    v[nr].next = lst[x];
    lst[x] = nr;
}

void start(int x0){
    for(int i = 1; i <= n; i++){
        d[i] = INF;
    }
    d[x0] = 0;
}

void swap_(int p1, int p2){
    swap(h[p1], h[p2]);
    pos[h[p1]] = p1;
    pos[h[p2]] = p2;
}

void push(int p){
    while(p > 1 and d[h[p]] < d[h[p >> 1]]){
        swap_(p, p >> 1);
        p >>= 1;
    }
}

void pull(int p){
    int fl = p << 1, fr = fl + 1, optim = p;
    if(fl <= nh and d[h[fl]] < d[h[optim]]){
        optim = fl;
    }
    if(fr <= nh and d[h[fr]] < d[h[optim]]){
        optim = fr;
    }
    if(optim != p){
        swap_(p, optim);
        pull(optim);
    }
}

void add_h(int x){
    h[++nh] = x;
    pos[x] = nh;
    push(nh);
}
void del_h(){
    swap_(1, nh--);
    if(nh == 0) return;
    pull(1);
}

int apm(){
    int x0 = 1, cost = 0;
    start(x0);
    add_h(x0);
    while(nh > 0){
        int x = h[1];
        cost += d[x];
        in_apm[x] = true;
        del_h();
        for(int p = lst[x]; p != 0; p = v[p].next){
            int y = v[p].node;
            int c = v[p].cost;
            if(!in_apm[y] and c < d[y]){
                d[y] = c;
                ant[y] = x;
                if(pos[y] != 0){
                    push(pos[y]);
                }
                else{
                    add_h(y);
                }
            }
        }
    }
    return cost;
}

void read(){
    in >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y, c;
        in >> x >> y >> c;
        add(x, y, c);
        add(y, x, c);
    }
}

int main()
{
    read();
    out << apm() << '\n' << n - 1 << '\n';
    for(int i = 2; i <= n; i++){
        out << ant[i] << " " << i << '\n';
    }
    return 0;
}