#include <bits/stdc++.h>
#define Nmax 200005
#define Mmax 400005
using namespace std;

int N, M;
int t[Nmax], h[Nmax];
vector<int> G[Nmax];
vector<pair<int, int> > apm;

/// retin muchiile grafului intr-un struct
struct edge{
   int x, y, c;
};
edge v[Nmax];

bool cmp(edge a, edge b) {   /// le vom sorta dupa cost
    return a.c < b.c;
}

int root(int x) {  /// obtine recursiv radacina unui element din DSU
   if (!t[x]) return x;
   return root(t[x]);
}
void unite(int x, int y) {   /// uneste 2 radacini
   if (h[x] < h[y]) swap(x, y);
   t[y] = x;
   if (h[x] == h[y]) ++h[x];
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        v[i] = {x, y, c};
    }
    sort(v + 1, v + M + 1, cmp);

    int apmCost = 0;
    for (int i = 1; i <= M; ++i)
        if (root(v[i].x) != root(v[i].y)) {
            apmCost += v[i].c;
            unite(root(v[i].x), root(v[i].y));
            apm.push_back({v[i].x, v[i].y});
        }

    fout << apmCost << "\n" << N - 1 << "\n";
    for (auto it: apm)
        fout << it.first << " " << it.second << "\n";



    return 0;
}