#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 20001;
const int maxm = 40001;

struct muchie
{
    int x, y, c;
};

void Read (muchie E[], int& N, int& M);

bool operator < (const muchie& x, const muchie& y)
{
    return x.c < y.c;
}

int Find (int x, int T[]);
void Merge (int x, int y, int T[], int R[]);
void Kruskal (muchie E[], int N, int M);

void Afis(muchie E[],int N,int M)
{
    cout<<N<<" "<<M<<endl;
     sort(E + 1, E + M + 1);
    for(int i=1;i<=M;i++)
        cout<<E[i].x<<" "<<E[i].y<<" "<<E[i].c<<endl;
}

int main()
{
    int N, M;
    muchie E[maxn];
    Read (E, N, M);
   // Afis(E,N,M);
    Kruskal(E, N, M);

    return 0;
}

void Read (muchie E[], int& N, int& M)
{
    ifstream fin ("apm.in");
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
        fin >> E[i].x >> E[i].y >> E[i].c;
    fin.close();
}

int Find (int x, int T[])
{
    if(T[x] == x)
        return x;
    T[x] = Find(T[x], T);

    return T[x];
}

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

void Kruskal (muchie E[], int N, int M)
{
    int R[maxn], T[maxn], k = 0, cost = 0;
    muchie APM [maxn - 1];

    for (int i = 1; i <= N; ++i)
        T[i] = i, R[i] = 0;

    sort(E + 1, E + M + 1);
    for (int i = 1; i <= M; ++i)
        if(Find(E[i].x, T) != Find(E[i].y, T))
        {
            cost += E[i].c;
            APM[++k] = E[i];

            Merge(Find(E[i].x, T), Find(E[i].y, T), T, R);
        }
    ofstream fout ("apm.out");

    fout << cost << '\n';
    fout << k << '\n';
    for (int i = 1; i < N; ++i)
        fout << APM[i].x << ' ' << APM[i].y << '\n';
        fout.close();

}