#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;

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

const int N = 200000;
const int M = 400000;
const int INF = 1e9;

int nr, cost, n;
int vf[M+1], urm[M+1], cst[M+1], lst[N+1];
int d[N+1], pred[N+1];
bool selectat[N+1];

int nh;
int h[N+1], poz[N+1];

void adauga_muchie(int x, int y, int c){
    vf[++nr] = y;
    cst[nr] = c;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void schimba(int p, int q){
    swap(h[p], h[q]);
    poz[h[p]] = p;
    poz[h[q]] = q;
}

void urca(int p){
    while(p>1 && d[h[p]] < d[h[p/2]]){
        schimba(p, p/2);
        p /= 2;
    }
}

void coboara(int p){
    int fs = 2*p;
    int fd = 2*p + 1;
    int bun = p;
    if(fs <= nh && d[h[fs]] < d[h[bun]])
        bun = fs;
    if(fd <= nh && d[h[fd]] < d[h[bun]])
        bun = fd;
    if(bun != p){
        schimba(p, bun);
        coboara(bun);
    }
}

void adauga(int x){
    h[++nh] = x;
    poz[x] = nh;
    urca(nh);
}

void sterge(int p){
    schimba(p, nh--);
    urca(p);
    coboara(p);
}

void prim(){
    for(int i=2; i<=n; i++){
        d[i] = INF;
        adauga(i);
    }
    d[1] = 0;
    adauga(1);
    while(nh > 0){
        int node = h[1];
        sterge(1);
        selectat[node] = true;
        cost += d[node];
        for(int p=lst[node]; p!=0; p=urm[p]){
            int next = vf[p];
            int c = cst[p];
            if(c < d[next] && !selectat[next]){
                d[next]  = c;
                pred[next] = node;
                urca(poz[next]);
            }
        }
    }
}

int main()
{
    int m,i,x,y,c;
    fin >> n >> m;
    for(i=0; i<m; i++){
        fin >> x >> y >> c;
        adauga_muchie(x, y, c);
        adauga_muchie(y, x, c);
    }
    prim();
    fout << cost << "\n" << n-1 << "\n";
    for(i=2; i<=n; i++)
        fout << i << " " << pred[i] << "\n";
    return 0;
}