#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#define NMAX 200001
#define MMAX 400001
#define BUFF_SIZE 100001

using namespace std;

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

struct triplet{
    int X, Y, C;
    triplet(){}
    triplet(int x, int y, int c)
    {
        X = x;
        Y = y;
        C = c;
    }
};

bool compare (const triplet T1, const triplet T2) { return T1.C < T2.C; }
vector <triplet> G;
int father[NMAX], height[NMAX];
bitset <MMAX> mark;
char buff[BUFF_SIZE];
int pos = 0;

void read (int &a)
{
    int _min = 1;
    while (!isdigit(buff[pos]))
    {
        if (buff[pos] == '-')
            _min = -1;
        if (++pos == BUFF_SIZE)
            in.read(buff, BUFF_SIZE), pos = 0;
    }
    a = 0;
    while (isdigit(buff[pos]))
    {
        a = a * 10 + (buff[pos] - '0');
        if (++pos == BUFF_SIZE)
            in.read(buff, BUFF_SIZE), pos = 0;
    }
    a = a * _min;
}

int det_father(int r)
{
    int aux = r;
    while (aux != father[aux])
        aux = father[aux];
    int y;
    while (r != father[r])
    {
        y = father[r];
        father[r] = aux;
        r = y;
    }
    return aux;
}

void unite(int f1, int f2)
{
    if (height[f1] < height[f2])
        father[f1] = f2;
    else
        father[f2] = f1;
    if (height[f1] == height[f2])
        height[f1]++;
}

int main()
{
    int n, m;
    read(n);
    read(m);
    int x, y, c;
    for (int i = 1; i <= n; ++i)
    {
        father[i] = i;
        height[i] = 0;
    }
    for (int i = 1; i <= m; ++i)
    {
        read(x), read(y), read(c);
        G.push_back(triplet(x, y, c));
    }
    in.close();
    sort (G.begin(), G.end(), compare);
    long long int ctotal = 0;
    int f1, f2, nr_t = 0;
    for (unsigned int i = 0; i < G.size(); ++i)
    {
        f1 = det_father(G[i].X);
        f2 = det_father(G[i].Y);
        if (f1 != f2)
        {
            ctotal += G[i].C;
            nr_t++;
            unite(f1, f2);
            mark.set(i);
        }
    }
    out << ctotal << "\n";
    out << nr_t << "\n";
    for (unsigned int i = 0; i < G.size(); ++i)
        if (mark.test(i))
            out << G[i].X << " " << G[i].Y << "\n";
    out.close();
    return 0;
}