#include<fstream>
#include<iostream>
#include<vector>
#define maxn 200005

using namespace std;

vector < pair<int,int> > v[maxn];
pair<int,int> mc[maxn];
int h[maxn], lh, pos[maxn], t[maxn], d[maxn];

void up(int k){
    int x = h[k];
    while (k > 1 && d[h[k/2]] > d[x]){
        h[k] = h[k/2];
        pos[h[k]] = k;
        k = k/2;    
    } 
    h[k] = x;
    pos[x] = k;
}

void down(int k){
    int son = 1, aux;
    while (son != 0){
        son = 0;
        if (k*2 <= lh){
            son = k*2;
            if (k*2+1 <= lh && d[h[k*2+1]] < d[h[son]])
                son = k*2+1;
            if (d[h[son]] > d[h[k]])
                son = 0;   
        }    
        if (son != 0){
            aux = h[son];
            h[son] = h[k];
            h[k] = aux;
            pos[h[k]] = k;
            pos[h[son]] = son;
            k = son;    
        }
    }
}

int main(){
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m, i, k, nod, x, y, cost, poz, c=0;
    f>>n>>m;
    for (i = 1; i <= m; i++){
        f>>x>>y>>cost;
        v[x].push_back(make_pair(y, cost));
        v[y].push_back(make_pair(x, cost));
    }
    
    for (i = 1; i <= n; i++){
        h[i] = i;
        pos[i] = i;
        d[i] = 1000000; 
    }

    t[1] = 0;
    d[1] = 0;
    
    lh = n;
    k = 0;
    pair<int,int> e;
    while (lh > 0){
        nod = h[1];
        c = c+d[nod];
        h[1] = h[lh];
        lh--;
        down(1);
        k++;
        mc[k] = make_pair(t[nod], nod);
        for (i = 0; i < v[nod].size(); i++){
            e = v[nod][i];
            if (d[e.first] > e.second){
                d[e.first] = e.second;
                t[e.first] = nod;
                poz = pos[e.first];
                up(poz);    
            }    
        }    
    }
    
    g<<c<<'\n'<<n-1<<'\n';
    for (i = 2; i <= n; i++)
        g<<mc[i].first<<" "<<mc[i].second<<'\n';
    
    return 0;
}