#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;
}