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

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
struct Edge
{
    int src, dest, weight;
};

struct Subset
{
    int parent;
    int rank;
};

class Graph
{
    int V;
    vector<Edge> edges;

public:
    Graph(int v) : V(v) {}

    void addEdge(int src, int dest, int weight)
    {
        Edge edge = {src, dest, weight};
        edges.push_back(edge);
    }

    int find(vector<Subset>& subsets, int i)
    {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);

        return subsets[i].parent;
    }

    void Union(vector<Subset>& subsets, int x, int y)
    {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else
        {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    void kruskalMST(ofstream& out)
    {
        vector<Edge> result;
        int e = 0, i = 0;
        sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b)
        {
            return a.weight < b.weight;
        });

        vector<Subset> subsets(V);
        for (int v = 0; v < V; v++)
        {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        int totalCost = 0;
        while (e < static_cast<int>(edges.size()) - 1 && i < edges.size())

        {
            Edge next_edge = edges[i++];
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            if (x != y)
            {
                result.push_back(next_edge);
                Union(subsets, x, y);
                totalCost += next_edge.weight;
                e++;
            }
        }

        out << totalCost << endl;
        out << result.size() << endl;
        for (auto& edge : result)
        {
            out << edge.src << " " << edge.dest << endl;
        }
    }
};

int main()
{


    int n, m;
    in >> n >> m;

    Graph g(n);

    for (int i = 0; i < m; i++)
    {
        int src, dest, weight;
        in >> src >> dest >> weight;
        g.addEdge(src, dest, weight);
    }

    g.kruskalMST(out);

    in.close();
    out.close();

    return 0;
}