#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5 + 5;

struct edge{
    int a, b, c;
};

bool cmp(edge a, edge b){
    return a.c < b.c;
}

vector <edge> g, sol;
int father[NMAX], mst = 0, depth[NMAX];

int root(int node){
    if(father[node] == 0)
        return node;
    else{
        int ax = root(father[node]);
        father[node] = ax;
        return ax;
    }
}

void uni(int a, int b){
    int ra, rb;

    ra = root(a);
    rb = root(b);

    if(depth[ra] > depth[rb])
        father[rb] = ra;
    else father[ra] = rb;
}

int main()
{
    int n, m;

    fin >> n >> m;

    for(int i = 1; i <= m; ++i){
        int a, b, c;

        fin >> a >> b >> c;
        g.push_back({a, b, c});
    }

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

    for(auto &it: g)
        if(root(it.a) != root(it.b)){
            uni(it.a, it.b);
            mst += it.c;
            sol.push_back(it);
        }

    fout << mst << '\n' << sol.size() << '\n';

    for(auto &it: sol)
        fout << it.a << ' ' << it.b << '\n';

    return 0;
}