#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) {}

    // ...

    int find(vector<int>& parent, int i)
    {
        if (parent[i] != i)
            parent[i] = find(parent, parent[i]);
        return parent[i];
    }
    void addEdge(int src, int dest, int weight) {
        Edge newEdge;
        newEdge.src = src;
        newEdge.dest = dest;
        newEdge.weight = weight;
        edges.push_back(newEdge);
    }
    void Union(vector<int>& parent, vector<int>& rank, int x, int y)
    {
        int xroot = find(parent, x);
        int yroot = find(parent, y);

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

    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<int> parent(V);
        vector<int> rank(V, 0);
        for (int v = 0; v < V; v++)
        {
            parent[v] = v;
        }

        int totalCost = 0;
        while (e < V - 1 && i < edges.size())
        {
            Edge next_edge = edges[i++];
            int x = find(parent, next_edge.src);
            int y = find(parent, next_edge.dest);

            if (x != y)
            {
                result.push_back(next_edge);
                Union(parent, rank, 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;
}