#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

struct edge{
    int x, y, w;
};

const int NMAX = 200005;
const int MMAX = 400005;
const char nl = '\n';

int n, m, father[NMAX], sum;

edge v[MMAX];

vector<edge> tree;

bool cmp(const edge& a, const edge& b){
    return a.w < b.w;
}

int root(int x){
    if(father[x] == x)
        return x;
    return father[x] = root(father[x]);
}

void unite(int x, int y){
    father[root(x)] = root(y);
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; ++i)
        in >> v[i].x >> v[i].y >> v[i].w;
    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= n; ++i)
        father[i] = i;
    for(int i = 1; i <= m; ++i){
        if(root(v[i].x) != root(v[i].y)){
            unite(v[i].x, v[i].y);
            tree.push_back({v[i].y, v[i].x, v[i].w});
            sum = sum + v[i].w;
        }
    }
    out << sum << nl << tree.size() << nl;
    for(auto i: tree){
        out << i.x << ' ' << i.y << nl;
    }
    return 0;
}