///Algoritmul lui Prim
#include <bits/stdc++.h>
#define NMAX 200005
#define pii pair< int, int >
#define piii pair < int, pii >
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, cost;
int parent[NMAX], card[NMAX];
bool ap[NMAX];
vector < pii > nod[NMAX], ans;
priority_queue < piii, vector < piii >, greater < piii > > pq;

void add_edges(int x){
    ap[x] = true;
    int y, c;
    for(auto it: nod[x]){
        y = it.first;
        c = it.second;
        if(ap[y])
            continue;
        pq.push({c, {y, x}});
    }
}

void answer(){
    add_edges(1);
    int c, x, y;
    while(ans.size() != n-1){
        c = pq.top().first;
        y = pq.top().second.first;
        x = pq.top().second.second;
        pq.pop();
        if(ap[y])
            continue;
        cost += c;
        ans.push_back({x, y});
        add_edges(y);
    }
}

void read(){
    f>>n>>m;
    int c, x, y;
    for(int i = 1; i <= m; ++i){
        f>>x>>y>>c;
        nod[x].push_back({y, c});
        nod[y].push_back({x, c});
    }
    answer();
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(auto it: ans)
        g<<it.first<<' '<<it.second<<'\n';
}

int main(){
    read();
    return 0;
}