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

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;

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;
    in >> n >> 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++)
    {
        in >> x >> y >> 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;
}