#include <iostream>
	
#include <fstream>
	
#include <vector>
	
#include <algorithm>
	
#define maxN 200005
	
 
	
using namespace std;
	
 
	
ifstream fin("apm.in");
	
ofstream fout("apm.out");
	
 
	
struct Edge {
	
    pair <int, int> vert;
	
    int cost;
	
    Edge (pair<int, int> v, int c) : vert(v), cost(c) {};
	
};
	
 
	
vector <Edge> G;
	
int n, m, tata[maxN], rang[maxN];
	
 
	
bool cmp (Edge a, Edge b) {
	
    return a.cost < b.cost;
	
}
	
 
	
void make_set (int nod) {
	
    rang[nod] = 0;
	
    tata[nod] = nod;
	
}
	
 
	
int find (int nod) {
	
    if (tata[nod] != nod) {
	
        return find(tata[nod]);
	
    }
	
    return nod;
	
}
	
 
	
int unesc (int root1, int root2) {
	
    if (rang[root1] > rang[root2]) {
	
        tata[root2] = root1;
	
    }
	
    else {
	
        if (rang[root1] < rang[root2]) {
	
            tata[root1] = root2;
	
        }
	
        else {
	
            tata[root1] = root2;
	
            rang[root2]++;
	
        }
	
    }
	
}
	
 
	
void Kruskal () {
	
    int root1, root2, sum = 0, s = 0;
	
    vector <Edge> arb;
	
    for (int i = 1; i <= n; ++i) {
	
        make_set(i);
	
    }
	
    sort(G.begin(), G.end(), cmp);
	
    for (int i = 0; i < m; ++i) {
	
        root1 = find(G[i].vert.first);
	
        root2 = find(G[i].vert.second);
	
        if (root1 != root2) {
	
            arb.push_back(G[i]);
	
            unesc(root1, root2);
	
            sum+= G[i].cost;
	
            s++;
	
        }
	
    }
	
    fout << sum << '\n';
	
    fout << s << '\n';
	
    for (int i = 0; i < s; ++i) {
	
        fout << arb[i].vert.first << " " << arb[i].vert.second << '\n';
	
    }
	
}
	
 
	
int main () {
	
    fin >> n >> m;
	
    int x, y, w;
	
    for (int i = 1; i <= m; ++i) {
	
        fin >> x >> y >> w;
	
        G.push_back(Edge({y, x}, w));
	
    }
	
    Kruskal();
	
}