#include <fstream>
#include <vector>
#define pb push_back
#define INF 0x7f7f7f7f

using namespace std;

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

struct vecin
{
    int j, c;
};

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

vector < vecin > V[200001];
int N, M;
int p[200001], Xn[200001];
muchie X[200000];
int costmin;

void citire()
{
    fin >> N >> M;
    int x, y, c;
    vecin a;

    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y >> c;
        a.j = y; a.c = c;
        V[x].pb(a);
        a.j = x;
        V[y].pb(a);
    }
}

void arbore()
{
    int k = 1;// incepem cu nodu 1
    Xn[1] = 1;// punem nodu 1 ca folosit
    p[1] = 1;// deci nodu 1 ii pus
    muchie minim;// cautam costu minim

    while(k <= N)// cat timp nu am pus toate nodurile
    {
        minim.c = INF;//initializam costu minim
        for(int i = 1; i <= k; i++)// mergem prin toate nodurile puse din Xn
            for(int j = 0; j < V[Xn[i]].size(); j++)// pentru fiecare nod ne uitam prin vecinii lui
                if(V[Xn[i]][j].c < minim.c && p[V[Xn[i]][j].j] == 0)// cautam minimul costului unei muchii care are un capat in nodurile puse si unu nu
                {
                    minim.x = Xn[i]; minim.y = V[Xn[i]][j].j; minim.c = V[Xn[i]][j].c;
                }

        p[minim.y] = 1;
        Xn[k + 1] = minim.y;
        X[k] = minim;
        costmin += minim.c;
        k++;
    }

}

int main()
{
    citire();
    arbore();
/*
    fout << N << " " << M << "\n";
    for(int i = 1; i <= N; i++)
    {
        fout << "NODUL " << i << " SE LEAGA DE NODUL\n";
        for(int j = 0; j < V[i].size(); j++)
            fout << V[i][j].j << " cu costu " << V[i][j].c << "\n";
    }
*/
    costmin -= INF;
    fout << costmin << "\n" << N - 1 << "\n";

    for(int i = 1; i < N; i++)
        fout << X[i].x << " " << X[i].y << "\n";


    fin.close();
    fout.close();
    return 0;
}