#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct Edge
{
    int x, y, w;
    friend bool operator<(Edge A, Edge B)
    {
        return A.w < B.w;
    }
};

struct DSU
{
    int n;
    vector<int> parent, rank;

    DSU() {}
    DSU(int _n) : n(_n)
    {
        parent.resize(n);
        rank.resize(n, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int FindRoot(int node)
    {
        if (node == parent[node])
            return node;
        return parent[node] = FindRoot(parent[node]);
    }

    void UnionSets(int node1, int node2)
    {
        node1 = FindRoot(node1);
        node2 = FindRoot(node2);
        if (node1 == node2)
            return;
        if (rank[node1] < rank[node2])
            swap(node1, node2);
        if (rank[node1] == rank[node2])
            rank[node1]++;
        parent[node2] = node1;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(NULL);

    int n, m;
    f >> n >> m;
    vector<Edge> edges(m);

    for (int i = 0; i < m; i++)
    {
        f >> edges[i].x >> edges[i].y >> edges[i].w;
        edges[i].x--;
        edges[i].y--;
    }

    auto Kruskal = [&](int &mst_cost) -> vector<Edge>
    {
        DSU dsu(n);
        vector<Edge> mst_edges;
        sort(edges.begin(), edges.end());
        for (int i = 0; i < m; i++)
            if (dsu.FindRoot(edges[i].x) != dsu.FindRoot(edges[i].y))
            {
                mst_cost += edges[i].w;
                mst_edges.push_back(edges[i]);
                dsu.UnionSets(edges[i].x, edges[i].y);
            }
        return mst_edges;
    };

    int mst_cost = 0;
    vector<Edge> mst_edges = Kruskal(mst_cost);

    g << mst_cost << '\n';
    g << n - 1 << '\n';
    for (Edge &edge : mst_edges)
        g << edge.x + 1 << ' ' << edge.y + 1 << '\n';
    return 0;
}