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

using namespace std;
struct muchie {
    int x, y, cost;
};
ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 200001;
vector<int> comp(NMAX + 1,-1);

bool cmp(muchie a, muchie b) {
    return a.cost < b.cost;
}

vector<muchie> muchii;
int N, M;

void citire() {
    fin >> N >> M;
    int x, y, c;
    for (int i = 1; i <= M; i++) {
        fin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }
}
int get_root(int x) {
    if (comp[x]>=0) return get_root(comp[x]);
    return x;
}
void pathCompression(int x, int root)
{
    while(comp[x]>=0)
    {
        int tmp = comp[x];
        comp[x] = root;
        x = tmp;
    }
}
bool disjoint(int x, int y)
{
    return get_root(x)!=get_root(y);
}
void unite(int x, int y)
{
    int xRoot = get_root(x);
    int yRoot = get_root(y);
    if(comp[xRoot] < comp[yRoot])
    {
        comp[xRoot]= yRoot;
        pathCompression(x,yRoot);
    }
    else if(comp[xRoot] > comp[yRoot])
    {
        comp[yRoot] = xRoot;
        pathCompression(y,xRoot);

    } else{
        comp[yRoot]= xRoot;
        comp[xRoot]--;
    }
}
int COST = 0;
vector<muchie> sol;
void Kruskal() {
    sort(muchii.begin(), muchii.end(), cmp);
    int cnt = 0, i = 0;
    while (cnt < N - 1) {
        int x = muchii[i].x, y = muchii[i].y;
        if (disjoint(x, y)) {
            unite(x, y);
            sol.push_back({x,y,muchii[i].cost});
            COST += muchii[i].cost;
            cnt++;
        }
        i++;

    }
}

int main() {
    citire();
    Kruskal();
    fout<<COST<<'\n'<<sol.size()<<'\n';
    for(auto s:sol)
        fout<<s.x<<" "<<s.y<<'\n';
    return 0;
}