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

using namespace std;

class DSet
{
public:
    vector<int> repr;
    void s_union(int x, int y)
    {
        if(repr[x] == repr[y])
            return;
        repr[repr[y]] = repr[x];
    }

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

    int findSet(int x)
    {
        vector<int> chain;
        while(repr[x] != x)
        {
            chain.push_back(x);
            x = repr[x];
        }
        for(int i = 0; i < chain.size(); ++i)
            repr[chain[i]] = x;
        return x;
    }

    DSet(int n)
    {
        for(int i = 0; i <= n; ++i)
            repr.push_back(i);
    }
};

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

    void print()
    {
        printf("%d %d\n", node1, node2);
    }

    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;
    scanf("%d", &n);
    scanf("%d", &m);
    vector<Edge> edges;
    vector<Edge> solution;
    for(int i = 0; i < m; ++i)
    {
        int x, y, cost;
        scanf("%d", &x);
        scanf("%d", &y);
        scanf("%d", &cost);
        edges.push_back(Edge(x, y, cost));
    }
    DSet dSet(n);

    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);
        }
    }

    printf("%d\n%d\n", totalCost, n - 1);
    for(int i = 0; i < solution.size(); ++i)
        solution[i].print();


    return 0;
}