#include <fstream>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N = 200005, M = 1999999999;
int vec[N], d[N], h[N], poz[N], af[N], af1[N];
vector <pair<int,int> > g[N];
void up_heap(int f){
    while(f/2 && d[h[f]] < d[h[f/2]]){
        swap(h[f], h[f/2]);
        swap(poz[h[f]], poz[h[f/2]]);
        f /= 2;
    }
}
void down_heap(int t, int &l){
    int f = 0;
    while(t != f){
        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_heap(int x, int &l){
    h[++l] = x;
    poz[x] = l;
    up_heap(l);
}
int extract_heap(int &l){
    int rad = h[1];
    poz[rad] = 0;
    swap(h[1],h[l--]);
    poz[h[1]] = 1;
    down_heap(1,l);
    return rad;
}
void insert_apm(int ns){
    int nr, c;
    for(int i=0;i<g[ns].size();i++){
        nr = g[ns][i].first;
        c = g[ns][i].second;
        if(d[nr] > c)
            d[nr] = c;
        if (d[nr] == c)
            vec[nr] = ns;
    }
}
void prim(int ns, int n, int &r, int l, int ind){
    int nr, 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];
        af[++ind] = rad;
        af1[ind] = vec[rad];
        for(int j=0;j<g[rad].size();j++){
            nr = g[rad][j].first;
            if (poz[nr])
                up_heap(poz[nr]);
        }
    }
}
int main()
{
    int n,m,x,y,z, r = 0;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        g[x].push_back(make_pair(y,z));
        g[y].push_back(make_pair(x,z));
    }
    in.close();
    prim(1,n,r,0,0);
    out<<r<<"\n"<<n-1<<"\n";
    for(int i=1;i<n;i++)
        out<<af[i]<<" "<<af1[i]<<"\n";
    out.close();
    return 0;
}