#include <bits/stdc++.h>

using namespace std;

const char* in  = "apm.in";
const char* out = "apm.out";
const int NMAX = 400005;

pair<int, int> P[NMAX];
int N, M, Total, TT[NMAX], k, RG[NMAX];

struct Edge
{
    int x, y, c;
}V[NMAX];

bool Cmp(Edge a, Edge b) {
    return a.c < b.c;
}

//DISJOINT SET
int Find(int v) {
    if(TT[v] == v)
        return v;
    return TT[v] = Find(TT[v]);
}

void Unite(int x, int y) {
    if(RG[x] < RG[y])
        TT[x] = y;
    if(RG[x] >RG[y])
        TT[y] = x;
    if(RG[x] == RG[y]) {
        TT[x] = y;
        RG[y]++;
    }
}

void Solve() {
    for(int i = 1; i <= M; ++i)
        if(Find(V[i].x) != Find(V[i].y)) {
            Unite(Find(V[i].x), Find(V[i].y));
            P[++k].first = V[i].x;
            P[k].second  = V[i].y;
            Total += V[i].c;
        }
}


int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL), cout.tie(NULL);

    freopen(in, "r", stdin);
    freopen(out, "w", stdout);

    cin >> N >> M;
    for(int i = 1; i <= M; ++i)
        cin >> V[i].x >> V[i].y >> V[i].c;
    sort(V + 1, V + M + 1, Cmp);

    for(int i = 1; i <= M; ++i) {
        TT[i] = i;
        RG[i] = 1;
    }

    Solve();

    cout << Total << '\n';
    cout << N-1 << '\n';
    for(int i = 1; i <= k; ++i)
        cout << P[i].first << ' ' << P[i].second << '\n';

    return 0;
}