#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

const int N_max = 200002;
const int M_max = 400002;

struct MUCHIE
{
    int x, y, cost; bool ales;
};
MUCHIE m[M_max];

int tata[N_max];
int h[N_max];

int cost_min;

int N, M;

int FIND(int x) // RETURNEAZA RADACINA NODULUI x
{
    int r, y;

    r = x;

    while(tata[r] != r) r = tata[r];

    while(tata[x] != x)
    {
        y = tata[x];

        tata[x] = r;

        x = y;
    }

    return r;
}

void UNION(int x, int y)
{
    int a = tata[x];
    int b = tata[y];

    if(h[a] < h[b]) tata[a] = b;
    else
    {
        tata[b] = a;

        if(h[a] == h[b]) h[a]++;
    }
}

bool exc(MUCHIE e1, MUCHIE e2)
{
    return e1.cost < e2.cost;
}

int main()
{
    int i, x, y, c, a, b, nr = 0;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y >> c;

        m[i].x = x;
        m[i].y = y;
        m[i].cost = c;
    }

    sort(m + 1, m + M + 1, exc);

    for(i = 1; i <= N; i++) tata[i] = i;

    for(i = 1; i <= M; i++)
    {
        a = m[i].x;
        b = m[i].y;

        a = FIND(a);
        b = FIND(b);

        if(a != b) // ALEG MUCHIA (m[i].x, m[i].y)
        {
            //out << m[i].x << " " << m[i].y << '\n';

            m[i].ales = true;

            cost_min += m[i].cost;

            nr++;

            UNION(a, b);
        }
    }

    out << cost_min << '\n';
    out << nr << '\n';

    nr = 0;

    for(i = 1; i <= M; i++)
        if(m[i].ales == true)
        {
            nr++;
            out << m[i].x << " " << m[i].y << '\n';

            if(nr == N - 1) break;
        }

    return 0;
}