#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMax = 400001;

pair<int, int> A[NMax];

int T[NMax], R[NMax];
int N, M, k, Cost;


struct Edge
{
    int x, y, w;
} G[NMax];

void read()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        fin >> G[i].x >> G[i].y >> G[i].w;
    }
}

int Find(int x)
{
    while(T[x] != x)
    {
        x = T[x];
    }

    return x;
}

void Unire(int x, int y)
{
    if(R[x] < R[y])
    {
        T[x] = y;
    }
    if(R[y] < R[x])
    {
        T[y] = x;
    }
    if(R[x] == R[y])
    {
        T[x] = y;
        R[y]++;
    }
}


void Rezolvare()
{
    for(int i = 1; i <= M; i++)
    {
        int tata_x = Find(G[i].x);
        int tata_y = Find(G[i].y);

        if(tata_x != tata_y)
        {
            Unire(tata_x, tata_y);
            A[++k].first = G[i].x;
            A[k].second = G[i].y;
            Cost += G[i].w;
        }

    }
}

bool sortare(Edge x, Edge y)
{
    return x.w < y.w;
}


int main()
{
    read();

    sort(G + 1, G + M + 1, sortare);

    for(int i = 1; i <= N; i++)
    {
        T[i] = i;
        R[i] = 1;
    }

    Rezolvare();


    fout << Cost << "\n" << N - 1 << "\n";

    for(int i = 1; i < N; i++)
    {
        fout << A[i].first << ' ' << A[i].second << "\n";
    }


    fin.close();
    fout.close();

    return 0;
}