#include <cstdio>
#include <algorithm>
#include <vector>

#define cost first
#define node1 second.first
#define node2 second.second
#define DIM 200010
using namespace std;

int nrNodes, nrEdges, K, value1, value2, sum, Root[DIM];
pair <int, pair <int, int> > Edges[DIM];
pair <int, pair <int, int> > newEdges[DIM];

inline int getRoot (int node)
{
    return (Root[node] < 0) ? node : getRoot (Root[node]);
}

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

    scanf ("%d %d", &nrNodes, &nrEdges);

    for (int i = 1; i <= nrEdges; i ++)
    {
        scanf ("%d", &Edges[i].node1);
        scanf ("%d", &Edges[i].node2);
        scanf ("%d", &Edges[i].cost );
    }

    sort (Edges + 1, Edges + nrEdges + 1);

    for (int i = 1; i <= nrNodes; i ++)
        Root[i] = -1;

    for (int i = 1; i <= nrEdges; i ++)
    {
        value1 = getRoot (Edges[i].node1);
        value2 = getRoot (Edges[i].node2);

        if (value1 != value2)
        {
            switch (Root[value1] - Root[value2] <= 0)
            {
                case 1: {Root[value1] += Root[value2]; Root[value2] = value1; break;}
                case 0: {Root[value2] += Root[value1]; Root[value1] = value2; break;}
            }

            sum += Edges[i].cost;
            newEdges[++K] = Edges[i];
        }
    }

    printf ("%d\n%d\n", sum, nrNodes - 1);

    for (int i = 1; i <= nrNodes - 1; i ++)
        printf ("%d %d\n", newEdges[i].node1, newEdges[i].node2);

    fclose (stdin );
    fclose (stdout);

    return 0;
}