#include <fstream>
#include <map>
#include <vector>

using namespace std;

const int MAXN = 200005, INF = 1 << 30;

vector<pair<int, int> >graf[MAXN], arb;
int minv[MAXN], cost[MAXN], heap[2 * MAXN], pos[MAXN];
int n, m, heapsz, ans;

void apm_push(int nod){
    for(auto x:graf[nod]){
        if(cost[x.first] > x.second){
            cost[x.first] = x.second;
            minv[x.first] = nod;
        }
    }
}

void heap_jos(int p){
    int f1 = 2 * p, f2 = 2 * p + 1, np = p;
    if(f1 <= heapsz && cost[heap[np]] > cost[heap[f1]]) np = f1;
    if(f2 <= heapsz && cost[heap[np]] > cost[heap[f2]]) np = f2;
    if(np != p){
        swap(heap[p], heap[np]);
        swap(pos[heap[p]], pos[heap[np]]);
        heap_jos(np);
    }
}

void heap_sus(int p){
    if(p == 1) return;
    if(cost[heap[p]] < cost[heap[p / 2]]){
        swap(heap[p], heap[p / 2]);
        swap(pos[heap[p]], pos[heap[p / 2]]);
    }
    heap_sus(p / 2);
}

void heap_push(int nod){
    heap[++heapsz] = nod;
    pos[nod] = heapsz;
    heap_sus(heapsz);
}

int heap_top(){
    int top = heap[1];
    swap(heap[1], heap[heapsz]);
    swap(pos[heap[1]], pos[heap[heapsz]]);
    heapsz--;
    heap_jos(1);
    pos[top] = 0;
    return top;
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
    }
    for(int i = 2; i <= n; ++i) cost[i] = INF;
    apm_push(1);
    for(int i = 2; i <= n; ++i) heap_push(i);
    for(int i = 1; i < n; ++i){
        int t = heap_top();
        apm_push(t);
        ans += cost[t];
        arb.push_back({t, minv[t]});
        for(auto x:graf[t]){
            int nod = x.first;
            if(pos[nod]) heap_sus(pos[nod]);
        }
    }
    fout << ans << "\n" << n - 1 << "\n";
    for(auto x:arb) fout << x.first << " " << x.second << "\n";
    return 0;
}