#include <bits/stdc++.h>

using namespace std;

const int DIM = 2e5 + 2;

int to[DIM];
int siz[DIM];

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

    bool operator < (const muchie& muchie2) const {
        return (c < muchie2.c);
    }
};

muchie v[2*DIM];
vector <pair <int, int> > tree;

int findN(int x){
    if (to[x] == x)
        return x;

    to[x] = findN(to[x]);
    return to[x];
}

void unite(int x, int y){
    x = findN(x);
    y = findN(y);

    if (siz[x] > siz[y])
        swap(x, y);

    to[x] = y;
    siz[y] += siz[x];
}


int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        to[i] = i;
        siz[i] = 1;
    }

    for (int i = 1; i <= m; i++){
        int x, y, c;
        cin >> x >> y >> c;

        v[i].x = x;
        v[i].y = y;
        v[i].c = c;
    }

    sort(v + 1, v + 1 + m);

    int totalcost = 0;
    for (int i = 1; i <= m; i++){
        if (findN(v[i].x) != findN(v[i].y)){
            unite(v[i].x, v[i].y);
            tree.push_back({v[i].x, v[i].y});
            totalcost += v[i].c;
        }
    }

    cout << totalcost << "\n" << tree.size() << "\n";

    for (auto i : tree)
        cout << i.first << " " << i.second << "\n";

}


/*
9 14
1 2 10
1 3 -11
2 4 11
2 5 11
5 6 13
3 4 10
4 6 12
4 7 5
3 7 4
3 8 5
8 7 5
8 9 4
9 7 3
6 7 11
*/