#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <string>

using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

struct node{
    int data, rang;
    node* father;
};

struct muchii {
    int x, y, cost;
};

const int maxn = 200000;

node* FIND(node* a);
void UNION(node* a, node* b);
bool cmp(muchii a, muchii b);
void solve();
void init();
void show();

int N, M;
node* nodes[maxn + 1];
muchii V[2 * maxn + 2];
int SOL_X[maxn + 1], SOL_Y[maxn + 1], SOL = 0, k;


int main()
{
    init();
    solve();
    show();
    return 0;
}

void init()
{
    fi >> N >> M;
    for (int i = 1;i <= N;i++)
    {
        nodes[i] = new node;
        nodes[i]->data = i;
        nodes[i]->rang = 0;
        nodes[i]->father = NULL;
    }

    for (int i = 1;i <= M;i++)
        fi >> V[i].x >> V[i].y >> V[i].cost;

    sort(V + 1, V + M + 1, cmp);
    return;
}

bool cmp(muchii a, muchii b)
{
    if (a.cost < b.cost)
        return true;
    return false;
}

void solve()
{
    for (int i = 1;i <= M;i++)
    {
        if (FIND(nodes[V[i].x]) != FIND(nodes[V[i].y]))
        {
            UNION(nodes[V[i].x], nodes[V[i].y]);
            SOL += V[i].cost;
            SOL_X[++k] = V[i].x;
            SOL_Y[k] = V[i].y;
        }
    }
    return;
}

void UNION(node* a, node* b)
{
    if (a->rang > b->rang)
    {
        while (b->father != NULL)
            b = b->father;
        nodes[b->data]->father = a;
    }
    else if (b->rang > a->rang)
    {
        while (a->father != NULL)
            a = a->father;
        nodes[a->data]->father = b;
    }
    else
    {
        while (a->father != NULL)
            a = a->father;
        nodes[a->data]->father = b;
        nodes[b->data]->rang++;
    }

}

node* FIND(node* a)
{
    node* n = nodes[a->data];
    if (n->father != NULL)
        n->father = FIND(n->father);
    else if (n->father == NULL)
        return n;
    return n->father;
}

void show()
{
    fo << SOL << "\n" << N - 1 << "\n";
    for (int i = 1;i <= k;i++)
        fo << SOL_Y[i] << ' ' << SOL_X[i] << "\n";
}