#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

class ListNode
{
public:
    int e;
    ListNode *next;
    ListNode *repr;
    ListNode(int x, ListNode *_next, ListNode *_repr)
    {
        e = x;
        next = _next;
        repr = _repr;
    }
    ListNode();
}*nullptr;

class DSet
{
public:
    map<int, ListNode* > nodeMap;
    void s_union(int x, int y)
    {
        if(nodeMap[x]->repr == nodeMap[y]->repr)
            return;
        ListNode* ptr1 = nodeMap[x];
        ListNode* newrepr = ptr1->repr;
        while(ptr1->next != nullptr)
            ptr1 = ptr1->next;
        ListNode* ptr2 = nodeMap[y]->repr;
        ptr1->next = ptr2;
        while(ptr2 != nullptr)
        {
            ptr2->repr = newrepr;
            ptr2 = ptr2->next;
        }
    }

    bool disjoint(int a, int b)
    {
        return findSet(a) != findSet(b);
    }

    void makeSet(int x)
    {
        ListNode *listNode = new ListNode(x, nullptr, nullptr);
        nodeMap[x] = listNode;
        nodeMap[x]->repr = nodeMap[x];
    }

    int findSet(int x)
    {
        return nodeMap[x]->repr->e;
    }
};

class Edge
{
    int node1;
    int node2;
    int cost;
public:
    Edge(int a, int b, int c)
    {
        node1 = a;
        node2 = b;
        cost = c;
    }

    void print()
    {
        cout << node1 << ' ' << node2 << '\n';
    }

    int getFirstNode()
    {
        return node1;
    }

    int getSecondNode()
    {
        return node2;
    }

    int getCost()
    {
        return cost;
    }

    static bool compare(Edge e1, Edge e2)
    {
        return e1.cost < e2.cost;
    }
};

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    vector<Edge> solution;
    for(int i = 0; i < m; ++i)
    {
        int x, y, cost;
        cin >> x >> y >> cost;
        edges.push_back(Edge(x, y, cost));
    }
    DSet dSet;
    for(int i = 1; i <= n; ++i)
    {
        dSet.makeSet(i);
    }

    sort(edges.begin(), edges.end(), Edge::compare);
    int totalCost = 0;
    for(int i = 0; i < m; ++i)
    {
        int node1 = edges[i].getFirstNode();
        int node2 = edges[i].getSecondNode();

        if(dSet.disjoint(node1, node2))
        {
            totalCost += edges[i].getCost();
            solution.push_back(edges[i]);
            dSet.s_union(node1, node2);
        }
    }

    cout << totalCost << '\n' << n - 1 << '\n';
    for(int i = 0; i < solution.size(); ++i)
        solution[i].print();


    return 0;
}