#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm> // Pentru sortare (opțional, doar pt estetică la output)
using namespace std;

const int INF = 1e9;

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


void Prim(vector<vector<pair<int, int>>> adj, int N){
      // Min-heap care stochează: {cost, {nod_curent, nod_parinte}}
    // Avem nevoie de nod_parinte ca să putem afișa muchia care a fost aleasă
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>> > pq;
    // pair<int, pair<int, int>> // ce fel de obiecte vom stoca in priority_queue, Structura arată așa: { cost, { nod_destinatie, nod_sursa } }.
    // vector<pair<int, pair<int, int>>> // priority_queue nu stochează datele direct "în aer", ci folosește un container standard în spate (de obicei un vector).
    // greater<pair<int, pair<int, int>>> > //greater: Inversează ordinea și transformă coada într-un Min-Heap
    //Acum, pq.top() îți va returna elementul care este "mai mic" conform comparatorului greater.

    vector<bool> visited(N + 1, false);
    
    // Pentru a stoca muchiile soluției (cele N-1 muchii)
    vector<pair<int, int>> mst_edges;
    int total_cost = 0;

    // Începem cu nodul 1. Cost 0, Părinte -1 (nu are)
    pq.push({0, {1, -1}});

    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();

        // { cost, { nod_destinatie, nod_sursa } }
        int cost = top.first;
        int u = top.second.first;
        int prev = top.second.second; // Nodul din care am venit

        // Dacă nodul e deja vizitat, îl ignorăm
        if (visited[u]) 
            continue;

        // Marchem nodul ca vizitat
        visited[u] = true;

        // Dacă nu e nodul de start, adăugăm muchia la soluție
        if (prev != -1) {
            total_cost += cost;
            mst_edges.push_back({prev, u});
        }

        // Adăugăm vecinii
        for (auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (!visited[v]) {
                // Adăugăm în coadă: costul, nodul destinație, și nodul curent (ca părinte)
                pq.push({weight, {v, u}});
            }
        }
    }

    // Afișare rezultate conform formatului din imagine
    fout << total_cost << "\n";
    fout << mst_edges.size() << "\n"; // Ar trebui să fie N-1

    for (auto &edge : mst_edges) {
        fout << edge.first << " " << edge.second << "\n";
    }
}



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

    // Lista de adiacență: adj[nod] = {vecin, cost}
    // Folosim N + 1 pentru că nodurile sunt indexate de la 1
    vector<vector<pair<int, int>>> adj(N + 1);

    for (int i = 0; i < M; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }


    Prim(adj, N);   
    return 0;
}