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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
// DSU data structure
//  path compression + rank by union

// disjoint set union
class DSU
{
private:
    int* parent;
    int* rank;

public:
    DSU(int n)
    {
        parent = new int[n];
        rank = new int[n];

        for (int i = 0; i < n; i++)
        {
            parent[i] = -1;
            rank[i] = 1;
        }
    }

    ~DSU() {
        delete[] parent;
        delete[] rank;
    }

    // Find function
    int find(int i)
    {
        if (parent[i] == -1)
            return i;

        return parent[i] = find(parent[i]);
    }
    // union function
    void unite(int x, int y)
    {
        int s1 = find(x);
        int s2 = find(y);

        if (s1 != s2)
        {
            if (rank[s1] < rank[s2])
            {
                parent[s1] = s2;
                rank[s2] += rank[s1];
            }
            else
            {
                parent[s2] = s1;
                rank[s1] += rank[s2];
            }
        }
    }
};

// clasa unui graf
class Graph
{
private:
    vector<vector<int>> edgelist;
    int V;

public:
    Graph(int V)
    {
        this->V = V;
    }

    void addEdge(int x, int y, int w)
    {
        edgelist.push_back({w, x, y});
    }

    void kruskals_mst()
    {
        vector<pair<int, int>> mst_edges;
        // 1. Sort all edges
        sort(edgelist.begin(), edgelist.end());

        // Initialize the DSU
        DSU s(V);
        int ans = 0;
        for (auto edge : edgelist)
        {
            int w = edge[0];
            int x = edge[1];
            int y = edge[2];

            // take that edge in MST if it does form a cycle
            if (s.find(x) != s.find(y))
            {
                s.unite(x, y);
                mst_edges.push_back(make_pair(x, y));
                ans += w;
            }
        }
        g << ans << '\n';

        int tot_edges = mst_edges.size();
        g << tot_edges << '\n';
        for(int i = 0; i < tot_edges; ++i) {
            g << mst_edges[i].first << " " << mst_edges[i].second << '\n';
        }

    }
};

int main()
{
//    Graph g(4);
//    g.addEdge(0, 1, 1);
//    g.addEdge(1, 3, 3);
//    g.addEdge(3, 2, 4);
//    g.addEdge(2, 0, 2);
//    g.addEdge(0, 3, 2);
//    g.addEdge(1, 2, 2);

     int n, m;
     f >> n >> m;

     Graph g(n);
     for (int i = 0; i < m; i++)
     {
         int x, y, w;
         f >> x >> y >> w;
         g.addEdge(x, y, w);
     }

    g.kruskals_mst();
    return 0;
}