#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

struct Edge
{
    int u, v, cost;
    bool operator<(const Edge &other) const
    {
        return cost < other.cost;
    }
};

vector<int> parent, rank_;

int find(int x)
{
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

bool unionSets(int x, int y)
{
    int rootX = find(x);
    int rootY = find(y);

    if (rootX == rootY)
        return false;

    if (rank_[rootX] < rank_[rootY])
        parent[rootX] = rootY;
    else if (rank_[rootX] > rank_[rootY])
        parent[rootY] = rootX;
    else
    {
        parent[rootY] = rootX;
        rank_[rootX]++;
    }
    return true;
}

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

    int n, m;
    fin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
    {
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }

    // Sort edges by cost
    sort(edges.begin(), edges.end());

    // Initialize DSU
    parent.resize(n + 1);
    rank_.resize(n + 1, 0);
    for (int i = 1; i <= n; i++)
        parent[i] = i;

    // Kruskal's algorithm
    int totalCost = 0;
    int edgesInMST = 0;
    vector<pair<int, int>> mstEdges;

    for (const Edge &e : edges)
    {
        if (unionSets(e.u, e.v))
        {
            totalCost += e.cost;
            edgesInMST++;
            mstEdges.push_back({e.u, e.v});
        }
    }

    // Write output
    fout << totalCost << "\n";
    fout << edgesInMST << "\n";
    for (const auto &edge : mstEdges)
    {
        fout << edge.first << " " << edge.second << "\n";
    }

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

    return 0;
}