#include <cstdio>
#include <vector>

using namespace std;

struct edge {int node; int cost;};
struct full_edge {int n1; int n2; int cost;};
const int MAXN = 200005;

FILE *out;

vector<edge> g[MAXN];
full_edge heap[2 * MAXN];
int sol[2*MAXN];
bool vis[MAXN];
int n;
int heap_size = 0;

void swapValues(int x, int y)
{
    full_edge t;
    t = heap[x];
    heap[x] = heap[y];
    heap[y] = t;
}

void addToHeap(full_edge e)
{
    heap[++heap_size] = e;
    int i = heap_size;
    while (i > 1 && e.cost < heap[i/2].cost)
    {
        swapValues(i, i/2);
        i = i/2;
    }
}

void deleteTop()
{
    heap[1] = heap[heap_size];
    --heap_size;
    int i = 1;
    int vmin;
    while (1)
    {
        vmin = i;
        if (2*i <= heap_size)
            if (heap[2*i].cost < heap[vmin].cost)
                vmin = 2*i;
        if (2*i+1 <= heap_size)
            if (heap[2*i+1].cost < heap[vmin].cost)
                vmin = 2*i+1;
        if (vmin != i)
        {
            swapValues(i, vmin);
            i = vmin;
        }
        else
            break;
    }
}

void addEdges(int node)
{
    edge e;
    full_edge fe;
    while (!g[node].empty())
    {
        e = g[node].back();
        g[node].pop_back();
        if (!vis[e.node])
        {
            fe.n1 = node;
            fe.n2 = e.node;
            fe.cost = e.cost;
            addToHeap(fe);
        }
    }
}

int main()
{
    FILE *in = fopen("apm.in", "r");
    out = fopen("apm.out", "w");

    int m;
    fscanf(in, "%d%d", &n, &m);

    edge e;
    for (int x, y, c, i = 1; i <= m; ++i)
    {
        fscanf(in, "%d%d%d", &x, &y, &c);
        e.cost = c;
        e.node = y;
        g[x].push_back(e);
        e.node = x;
        g[y].push_back(e);
    }

    vis[1] = 1;
    addEdges(1);

    int cost_tot = 0;
    full_edge top;
    for (int i = 1; i < n;)
    {
        top = heap[1];
        deleteTop();
        if (!vis[top.n2])
        {
            vis[top.n2] = 1;
            cost_tot += top.cost;
            sol[2*i] = top.n1;
            sol[2*i+1] = top.n2;
            ++i;
            addEdges(top.n2);
        }
    }

    fprintf(out, "%d\n%d\n", cost_tot, n-1);
    for (int i = 1; i < n; ++i)
        fprintf(out, "%d %d\n", sol[2*i], sol[2*i+1]);

    return 0;
}