#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMax = 200005;

int v[NMax], h[NMax];

int rad(int x){
    if(v[x] == 0){
        return x;
    }
    else{
        int t = rad(v[x]);
        v[x] = t;
        return t;
    }
}

void unite(int x, int y){
    int radX = rad(x), radY = rad(y);
    if(h[radX] > h[radY]){
        v[radY] = radX;
        h[radX] += h[radY];
        rad(y);
    }
    else{
        v[radX] = radY;
        h[radY] += h[radX];
        rad(x);
    }
}

struct Muchie{
    int x, y, cost;
    Muchie(int x, int y, int cost): x(x), y(y), cost(cost) {}
    bool operator<(const Muchie& other) const{
        return this -> cost > other.cost;
    }
};

priority_queue<Muchie> q;
queue<Muchie> ans;

int main()
{
    int N, M, ctFinal = 0;
    fin >> N >> M;
    for(int i = 1; i <= N; ++ i){
        v[i] = 0;
        h[i] = 1;
    }
    for(int x, y, cost, i = 1; i <= M; ++ i){
        fin >> x >> y >> cost;
        q.emplace(x, y, cost);
    }
    while(!q.empty()){
        int x = q.top().x, y = q.top().y, cost = q.top().cost;
        if(rad(x) != rad(y)){
            unite(x, y);
            ans.emplace(x, y, cost);
            ctFinal += cost;
        }
        q.pop();
    }
    fout << ctFinal << '\n' << ans.size() << '\n';
    while(!ans.empty()){
        fout << ans.front().x << ' ' << ans.front().y << '\n';
        ans.pop();
    }
    return 0;
}