#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200005
#define mmax 400005

using namespace std;

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

int n, m, P[nmax], h[nmax], cost, edges;
bool check[mmax];

struct graf{
    int a, b, c;
}d;

vector <graf > v;

int find(int x){
    if(P[x] != x) P[x] = find(P[x]);
    return P[x];
}

void unite(int x, int y){
    int Rx = find(x);
    int Ry = find(y);
    if (h[Rx] > h[Ry]){
        P[y] = Rx;
        h[Rx] += h[Ry];
    }
    else{
        P[x] = Ry;
        h[Ry] += h[Rx];
    }
}

bool cmp(graf k, graf l) { return (k.c < l.c); }

void Kruskal(){
    for (int i = 1; i <= n; i++)
        P[i] = i, h[i] = 1;

    sort(v.begin(), v.end(), cmp);

    for (int i = 0; i < int(v.size()); i++)
        if (find(v[i].a) != find(v[i].b)){
            unite(v[i].a, v[i].b);
            cost += v[i].c;
            edges++;
            check[i] = true;
        }

}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        fin >> d.a >> d.b >> d.c;
        v.push_back(d);
    }

    Kruskal();

    fout << cost << '\n' << edges << '\n';
    for (int i = 0; i < int(v.size()); i++)
        if (check[i]) fout << v[i].a << " " << v[i].b << '\n';

    return 0;
}