#include <bits/stdc++.h>

using namespace std;

struct muchie{
    int x, y, c;
};

muchie v[400000];
int rad[200001];
int card[200001];
pair<int, int> sol[200000];
int solPos, sum;
int n, m;

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

muchieSort(muchie a, muchie b){
    if(a.c != b.c)
        return a.c < b.c;
    else
        return a.x < b.y;
}

int Find(int a){
    if(rad[a] == a)/// daca am ajuns la PRIMUL radical
        return a;
    rad[a] = Find(rad[a]); /// continui sa sap recursiv si actualizez rad[a]
    return rad[a];
}
int unite(int a, int b){ /// are sens numai daca este aplicata radacinii unei multimi !!!!!
    if (card[Find(a)] > card[Find(b)])
        swap(a, b);
    card[b] += card[a];
    rad[a] = b;
}


int main()
{
    in >> n >> m;
    for(int i = 0; i < m; i ++){
        in >> v[i].x >> v[i].y >> v[i].c;
    }

    for(int i = 1; i < n; i ++){
        rad[i] = i;
        card[i] = 1;
    }///setez card si rad


    sort(v, v+m, muchieSort);
    for(int i = 0; i < m; i ++){
        if(Find(v[i].x) != Find(v[i].y)){
            unite(Find(v[i].x), Find(v[i].y));

            sum += v[i].c;
            sol[solPos].first = v[i].x;
            sol[solPos].second = v[i].y;
            solPos ++;
            /// adaug muchia la solutie si dau unite
        }
        else{
            while (Find(v[i].x) == Find(v[i].y) && i < m){
                i++;
            }
            unite(v[i].x, v[i].y);

            sum += v[i].c;
            sol[solPos].first = v[i].x;
            sol[solPos].second = v[i].y;
            solPos ++;
            /// adaug muchia si dau unite
        }
    }

    out << sum << endl << n-1 << endl;
    for(int i = 0; i < n; i ++){
        out << sol[i].first << " " << sol[i].second << endl;
    }

    return 0;
}
//sortez muchiile, construiesc paduri de mult disj cu muchiile ordonate, nu adaug muchie daca creez ciclu, ma opresc daca gasesc n-1 muchii


/// functia de Find x, union x, pt sort cu structx, vector de muchii gasite pana acum, constructia padurii de mult