/*#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 2e5 + 1, M = 4e5;
int n, m, costt;
int t[N], nr[N];
pair<int, int> ans[N];
struct muchie{
    int x, y, cost;
    bool operator < (muchie muc) const{
        return cost < muc.cost;
    }
}e[M];

int radacina(int x){
    if(t[x] == 0)
        return x;

    t[x] = radacina(t[x]);
    return t[x];
}

void reuneste(int x, int y){
    int rx = radacina(x);
    int ry = radacina(y);
    if(nr[rx] > nr[ry]){
        t[ry] = rx;
        nr[rx] += nr[ry];
        //
    }else{
        t[rx] = ry;
        nr[ry] += nr[rx];
        //h[ry] = max(h[ry], h[rx] + 1); // practic doar pt. cazul in care h[rx] == h[ry]
    }
}

// M logM + N logN
int main(){
    f >> n >> m;
    for(int i = 0; i < m; i++)
        f >> e[i].x >> e[i].y >> e[i].cost;

    f.close();

    sort(e, e + m);
    for(int i = 1; i <= n; i++)
        nr[i] = 1;

    for(int i = 0, j = 1; i < m && j < n; i++){
        if(radacina(e[i].x) != radacina(e[i].y)){
            reuneste(e[i].x, e[i].y);
            costt += e[i].cost;
            ans[j] = {e[i].x, e[i].y};
            j++;
        }
    }

    // aici am verifica daca avem n - 1 muchii (in caz contrar avem graf care nu e conex)
    g << costt << '\n'
      << n - 1 << '\n';
    for(int i = 1; i < n; i++)
        g << ans[i].first << ' ' << ans[i].second << '\n';

    g.close();
}*/
#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 1, M = 4e5;
int n, m, costt;
int t[N], nr[N];
pair<int, int> ans[N];
struct muchie{
    int x, y, cost;
    bool operator < (muchie muc) const{
        return cost < muc.cost;
    }
}e[M];

int radacina(int x){
    if(t[x] == 0)
        return x;

    t[x] = radacina(t[x]);
    return t[x];
}

void reuneste(int x, int y){
    int rx = radacina(x);
    int ry = radacina(y);
    if(nr[rx] > nr[ry]){
        t[ry] = rx;
        nr[rx] += nr[ry];
    }else{
        t[rx] = ry;
        nr[ry] += nr[rx];
    }
}

int main(){
    f >> n >> m;
    for(int i = 0; i < m; i++)
        f >> e[i].x >> e[i].y >> e[i].cost;

    f.close();

    sort(e, e + m);
    for(int i = 1; i <= n; i++)
        nr[i] = 1;

    for(int i = 0, j = 1; i < m && j < n; i++){
        if(radacina(e[i].x) != radacina(e[i].y)){
            reuneste(e[i].x, e[i].y);
            costt += e[i].cost;
            ans[j] = {e[i].x, e[i].y};
            j++;
        }
    }

    g << costt << '\n'
      << n - 1 << '\n';
    for(int i = 1; i < n; i++)
        g << ans[i].first << ' ' << ans[i].second << '\n';

    g.close();
}