#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N = 200005, M = 1999999999;
int h[N], poz[N], d[N], vec[N], af[N][3];
struct nod{
    int nr,cost;
    nod *urm;
}*v[N];
void adaug(int x, int y, int z){
    nod *p = new nod;
    p->nr = y;
    p->cost = z;
    p->urm = v[x];
    v[x] = p;
}
void up_heap(int f){
    while(f/2 && d[h[f]] < d[h[f/2]]){
        swap(h[f],h[f/2]);
        poz[h[f]] = f;
        poz[h[f/2]] = f/2;
        f /= 2;
    }
}
void down_heap(int t, int l){
    int f = 0;
    while(f != t){
        f = t;
        if(f*2 <= l && d[h[t]] > d[h[f*2]])
            t = f * 2;
        if(f*2 + 1 <= l && d[h[t]] > d[h[f*2 + 1]])
            t = f * 2 + 1;
        swap(h[t],h[f]);
        poz[h[t]] = t;
        poz[h[f]] = f;
    }
}
void insert_apm(int ns){
    for(nod *nou = v[ns];nou;nou = nou->urm){
        if(d[nou->nr] > nou->cost)
            d[nou->nr] = nou->cost;
        if(d[nou->nr] == nou->cost)
            vec[nou->nr] = ns;
    }
}
void insert_heap(int x, int &l){
    h[++l] = x;
    poz[x] = l;
    up_heap(l);
}
void insert_af(int &ind, int rad){
    af[++ind][1] = rad;
    af[ind][2] = vec[rad];
}
int extract_heap(int &l){
    int rad = h[1];
    poz[rad] = 0;
    swap(h[1],h[l--]);
    down_heap(1,l);
    poz[h[1]] = 1;
    return rad;
}
void prim(int ns, int &l, int n, int &r, int &ind){
    int rad;
    for(int i=1;i<=n;i++)
        d[i] = M;
    d[ns] = 0;
    insert_apm(ns);
    for(int i=1;i<=n;i++)
        if(i != ns)
            insert_heap(i,l);
    for(int i=1;i<n;i++){
        rad = extract_heap(l);
        insert_apm(rad);
        r += d[rad];
        insert_af(ind,rad);
        for(nod *p = v[rad];p;p = p->urm)
            if(poz[p->nr])
                up_heap(poz[p->nr]);
    }
}
int main()
{
    int n,m,x,y,z, ns = 1, l = 0, r = 0, ind = 0;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        adaug(x,y,z);
        adaug(y,x,z);
    }
    in.close();
    prim(ns,l,n,r,ind);
    out<<r<<"\n"<<n-1<<"\n";
    for(int i=1;i<=ind;i++)
        out<<af[i][1]<<" "<<af[i][2]<<"\n";
    out.close();
    return 0;
}