#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

#define INF 0x3f3f3f3f
#define MAXN 200000

int n, m;
int d[MAXN], tata[MAXN];
bool fol[MAXN];
vector< pair<int, int> > graf[MAXN];
priority_queue< pair<int, int> > coada;

void prim(int st) {
    int i, crt_nod, crt_cost, urm_nod, urm_cost;
    for(i=1; i<=n; i++)
        d[i] = INF;
    
    d[st] = 0;
    coada.push(make_pair(0, st));
    while(!coada.empty()) {
        crt_nod = coada.top().second; fol[crt_nod] = true;
        crt_cost = -coada.top().first;
        coada.pop();
        
        if(crt_cost > d[crt_nod])
            continue;
        
        for(i=0; i<graf[crt_nod].size(); i++) {
            urm_nod = graf[crt_nod][i].second;
            urm_cost = graf[crt_nod][i].first;
            
            if(!fol[urm_nod] && d[urm_nod] > urm_cost) {
                d[urm_nod] = urm_cost;
                tata[urm_nod] = crt_nod;
                coada.push(make_pair(-urm_cost, urm_nod));
            }
        }
    }
    
    int costRasp = 0;
    for(i=1; i<=n; i++)
        costRasp += d[i];
    
    cout<<costRasp<<"\n"<<n-1<<"\n";
    
    for(i=2; i<=n; i++)
        cout<<i<<" "<<tata[i]<<"\n";
}

int main() {
    int i, x, y, z;
    cin >> n >> m;
    
    for(i=1; i<=m; i++) {
        cin >> x >> y >> z;
        graf[x].push_back( make_pair(z, y));
        graf[y].push_back( make_pair(z, x));
    }
    
    prim(1);
    
    return 0;
}