//Prim
// #include <bits/stdc++.h>
// #include <fstream>
// using namespace std;
//
// vector<pair<int,int>> adj[200001];
// int parent[200001];       // Vector pentru părinți (nu e folosit în final)
// int viz[200001];
//
// ifstream fin("apm.in");
// ofstream fout("apm.out");
//
// int main() {
//     int n, m;
//     fin >> n >> m;
//
//     for (int i=1;i<=n;i++) {
//         viz[i]=0;
//         parent[i]=-1;
//     }
//
//     int x, y, c;
//     for (int i = 1; i <=m; i++) {
//         fin >> x >> y >> c;
//         adj[x].push_back({y, c});
//         adj[y].push_back({x, c});
//     }
//
//     // Coada de priorități folosită de algoritmul lui Prim:
//     // (cost, nod curent, părinte)
//     priority_queue<
//         tuple<int,int,int>,
//         vector<tuple<int,int,int>>,
//         greater<tuple<int,int,int>>
//     > pq;
//
//     // Începem arborele din nodul 1, cu cost 0 și fără părinte
//     pq.push({0, 1, -1});
//
//     long long totalCost = 0;              // Cost total al APM
//     vector<pair<int,int>> edges;          // Muchiile din APM
//     edges.reserve(n - 1);
//
//     // Algoritmul lui Prim
//     while (pq.size()>0) {
//         auto [cost, nod, par] = pq.top();
//         pq.pop();
//
//         // Dacă nodul este deja inclus în APM, îl ignorăm
//         if (viz[nod]==1) continue;
//
//         viz[nod] = 1;         // Marchează nodul ca selectat în arbore
//         totalCost += cost;        // Adăugăm costul muchiei folosite
//
//         // Dacă nu este nodul de start, adăugăm muchia în lista soluției
//         if (par != -1) {
//             edges.push_back({par, nod});
//         }
//
//         // Explorăm muchiile care pleacă din nod
//         for (auto [vecin,pondere] : adj[nod]) {
//             if (viz[vecin]==0) {
//                 // Adăugăm în coada de priorități candidatul pentru APM
//                 pq.push({pondere, vecin, nod});
//             }
//         }
//     }
//
//     fout<<totalCost<<"\n";
//     fout<<edges.size()<<"\n";     // Nr de muchii în APM (trebuie să fie N - 1)
//     for (auto [u,v] : edges) {
//         fout<<u<<" "<< v<< "\n";
//     }
//
//     return 0;
// }

//Kruscal

#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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


struct muchie {
    int x,y,cost;
};

vector<int> parinte;
vector<int> sz;

void initializeaza_DSU(int n) {
    parinte.resize(n+1);
    sz.resize(n+1);

    for (int i = 1; i <= n; i++) {
        parinte[i] = i;
        sz[i] = 1;
    }
}

int gaseste(int x) {
    if (x == parinte[x])
        return x;
    return parinte[x] = gaseste(parinte[x]);
}

void unifica(int a, int b) {
    if (sz[a] < sz[b])
        swap(a,b);
    parinte[b] = a;
    sz[a] += sz[b];
}

bool arbore(int u, int v) {
    int a = gaseste(u);
    int b = gaseste(v);

    if (a == b) {
        return false;
    }
    unifica(a,b);
    return true;
}

int main() {
    int N,M;
    fin>>N>>M;

    vector<muchie> muchii(M);

    for (int i = 0; i < M; i++) {
        int x,y,c;
        fin>>x>>y>>c;
        muchii[i] = {x,y,c};
    }

    sort(muchii.begin(), muchii.end(), [](muchie a, muchie b) {
        return a.cost < b.cost;
    });

    initializeaza_DSU(N);

    int costTotal = 0;
    vector<pair<int,int>> rezultat;

    for (auto &m: muchii) {
        if (arbore(m.x,m.y)) {
            costTotal += m.cost;
            rezultat.push_back(make_pair(m.x,m.y));
        }
    }

    fout<<costTotal<<endl;
    fout<<rezultat.size()<<endl;
    for (auto &m: rezultat) {
        fout<<m.first<<" "<<m.second<<endl;
    }
}