//
// Created by avoro on 11/17/2025.
//
#include <algorithm>
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <climits>
using namespace std;

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

///prim
// int main() {
//     int n,m,x,y,c;
//     fin>>n>>m;
//     vector<vector<pair<int,int>>> adj(n+1);
//     vector<int> dist(n+1,INT_MAX);
//     vector<int> parinte(n+1,-1);
//     for (int i = 0; i< m ;i++) {
//         fin>>x>>y>>c;
//         adj[x].push_back(make_pair(y,c));
//         adj[y].push_back(make_pair(x,c));
//     }
//     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
//     dist[1] = 0;
//     vector<bool> used(n+1,false);
//     pq.push(make_pair(0,1));
//     vector<pair<int,int>> muchii;
//     int cost = 0;
//     while (!pq.empty()) {
//         pair<int,int> p = pq.top();
//         pq.pop();
//         if (used[p.second] == true) continue;
//         used[p.second] = true;
//         cost = cost + dist[p.second];
//
//         if (parinte[p.second] != -1) {
//             muchii.push_back(make_pair(parinte[p.second],p.second));
//         }
//         for (auto [v,w] : adj[p.second]) {
//             if (dist[v] > w && used[v] == false) {
//                 dist[v] = w;
//                 parinte[v] = p.second;
//                 pq.push(make_pair(dist[v],v));
//             }
//         }
//     }
//     fout<<cost<<endl;
//     fout<<muchii.size()<<endl;
//     for (auto [n1,n2] : muchii) {
//         fout<<n1<<" "<<n2<<endl;
//     }
// }

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

//vectorii dsu
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; //fiecare multime are marimea 1 la inceput
    }
}

//gaseste reprezentantul unei multimi si path compression
int gaseste(int x) {
    if (x == parinte[x])
        return x;
    return parinte[x] = gaseste(parinte[x]);
}

//unifica cele doua multimi folosind size, marimea multimii
int 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;
    }
}