#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 200005;

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

int n, m, cost;
int rang[nmax], parent[nmax];
vector <edge> v;
vector <pair<int,int> > rsp;

void read(){
    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        v.push_back({x, y , c});
    }
}

void init(){
    for(int i = 1; i <= n; i++){
        rang[i] = 1;
        parent[i] = i;
    }
}

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

int root(int nod){
    if(nod != parent[nod])
        parent[nod] = root(parent[nod]);
    return parent[nod];
}

void mk_union(int a, int b){
    if(rang[a] > rang[b])
        parent[b] = a;
    else
        parent[a] = b;

    if(rang[a] == rang[b])
        rang[b]++;
}

void solve(){
    for(int i = 0; i < v.size(); i++){
        edge it = v[i];
        if(root(it.x) != root(it.y)){
            cost += it.c;
            mk_union(root(it.x), root(it.y));
            rsp.push_back(make_pair(it.x, it.y));
        }
    }
}

void print(){
    fout << cost << "\n";
    fout << rsp.size() << "\n";

    for(int i = 0; i < rsp.size(); i++)
        fout << rsp[i].first << " " << rsp[i].second << "\n";
}

int main()
{
    read();
    init();
    sort(v.begin(), v.end(), cmp);
    solve();
    print();

    return 0;
}