#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

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

#define cin fin
#define cout fout

class DisjointSets
{
private:
    vector<size_t> sizeOfSet{0};
    vector<size_t> parent{0};

public:
    DisjointSets(const int &n)
    {
        sizeOfSet.resize(n + 1, 1);
        parent.resize(n + 1);

        for (size_t i = 0; i < n; i++)
        {
            parent[i] = i;
        }
    }

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

        return parent[x] = findSet(parent[x]);
    }

    void unionSets(int a, int b)
    {
        a = findSet(a);
        b = findSet(b);

        if (a == b)
        {
            return;
        }

        if (sizeOfSet[a] > sizeOfSet[b])
        {
            swap(a, b);
        }

        parent[b] = a;
        sizeOfSet[a] += sizeOfSet[b];
    }
};

struct Edge
{
    int a, b, cost;
};

istream &operator>>(istream &is, Edge &e)
{
    is >> e.a >> e.b >> e.cost;

    return is;
}

int main()
{
    ios::sync_with_stdio(false);

    size_t n, m;
    cin >> n >> m;

    vector<Edge> edges(m);

    for (size_t i = 0; i < m; i++)
    {
        cin >> edges[i];
    }

    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b)
         { return a.cost < b.cost; });

    DisjointSets ds(n);

    int totalCost = 0;
    vector<Edge> chosenEdges;
    chosenEdges.reserve(n);

    for (auto &&edge : edges)
    {
        if (ds.findSet(edge.a) != ds.findSet(edge.b))
        {
            ds.unionSets(edge.a, edge.b);

            chosenEdges.push_back(edge);
            totalCost += edge.cost;
        }
    }

    cout << totalCost << "\n";
    cout << chosenEdges.size() << "\n";

    for (auto &&edge : chosenEdges)
    {
        cout << edge.a << " " << edge.b << "\n";
    }

    return 0;
}