#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#include <array>
#include <stack>
#include <algorithm>

#define maxSize 100001

using namespace std;

vector<vector<pair<int, int>>> readAdjacencyListWeighted(ifstream& fin, int nodes, int edges, bool isDirected = false) {
    vector<vector<pair<int, int>>> adjList(nodes + 1);
    for (int i = 0; i < edges; i++) {
        int x, y, weight;
        fin >> x >> y >> weight;
        adjList[x].emplace_back(y, weight);
        if (!isDirected) {
            adjList[y].emplace_back(x, weight);
        }
    }
    return adjList;
}

vector<array<int, 3>> prim(int nodes, const vector<vector<pair<int, int>>>& adjList, int& cost) {
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    bitset<maxSize> marked;
    vector<array<int, 3>> mst;

    marked[1] = true;
    for (const auto& [adjNode, weight] : adjList[1]) {
        pq.push({weight, 1, adjNode});
    }

    while (!pq.empty() && mst.size() < nodes - 1) {
        auto [weight, u, v] = pq.top();
        pq.pop();

        if (marked[v]) {
            continue;
        }

        mst.push_back({u, v, weight});
        marked[v] = true;
        cost += weight;

        for (const auto& [adjNode, adjWeight] : adjList[v]) {
            if (!marked[adjNode]) {
                pq.push({adjWeight, v, adjNode});
            }
        }
    }

    if (mst.size() != nodes - 1) {
        cerr << "Graful nu este conex. Nu se poate construi un MST complet.\n";
        return {};
    }

    return mst;
}

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

    int finalCost = 0;
    int nodes, edges;
    fin >> nodes >> edges;

    auto edgeList = readAdjacencyListWeighted(fin, nodes, edges);

    auto mst = prim(nodes, edgeList, finalCost);

    if (!mst.empty()) {
        fout << finalCost << endl;
        fout << mst.size() << endl;
        for (auto elem : mst) {
            fout << elem[0] << " " << elem[1] << endl;
        }
    }

    fin.close();
    fout.close();

    return 0;
}