#include <fstream>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N = 200005, M = 1999999999;
int d[N], h[N], poz[N], pred[N];
vector <pair <int,int>> v[N], af;
void upHeap(int f){
    while(f/2 && d[h[f]] < d[h[f/2]]){
        swap(poz[h[f]], poz[h[f/2]]);
        swap(h[f], h[f/2]);
        f = f/2;
    }
}
void downHeap(int l){
    int t = 1, f = 0;
    while(t != f){
        f = t;
        if(f*2 <= l && d[h[f*2]] < d[h[t]])
            t = f*2;
        if(f*2 + 1 <= l && d[h[f*2+1]] < d[h[t]])
            t = f*2+1;
        swap(poz[h[t]], poz[h[f]]);
        swap(h[f],h[t]);
    }
}
void insertHeap(int val, int &l){
    h[++l] = val;
    poz[val] = l;
    upHeap(l);
}
int extractTop(int &l){
    int rad = h[1];
    poz[h[1]] = 0;
    swap(h[1], h[l--]);
    poz[h[1]] = 1;
    downHeap(l);
    return rad;
}
void updateAPM(int ns){
    int sz = v[ns].size(), nbr, c;
    for(int i=0;i<sz;i++){
        nbr = v[ns][i].first;
        c = v[ns][i].second;
        if(d[nbr] > c)
            d[nbr] = c;
        if(d[nbr] == c)
            pred[nbr] = ns;
    }
}
int prim(int n){
    int l = 0, rez = 0, rad, sz;
    for(int i=2;i<=n;i++)
        d[i] = M;
    updateAPM(1);
    for(int i=2;i<=n;i++)
        insertHeap(i,l);
    for(int i=1;i<n;i++){
        rad = extractTop(l);
        sz = v[rad].size();
        updateAPM(rad);
        rez += d[rad];
        af.push_back({pred[rad], rad});
        for(int j=0;j<sz;j++)
            if(poz[v[rad][j].first])
                upHeap(poz[v[rad][j].first]);
    }
    return rez;
}
int main()
{
    int n, m, x, y, z;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    in.close();
    out<<prim(n)<<"\n"<<n-1<<"\n";
    for(int j=0;j<af.size();j++)
        out<<af[j].first<<" "<<af[j].second<<"\n";
    out.close();
    return 0;
}