#include  <bits/stdc++.h>

using namespace std;

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

struct muchii
{
    int x,y,cost;

}muchia[400001];

struct arb
{///muchiile ce formeaza aborele
 int st,dr;

}arbore[400001];

int n,m,cost_total, poz,tata[200001] , rang[200001];


bool compara_costuri( muchii a,  muchii b)
{ ///sortam in ordine crescatoare in functie de costul muchiei
    return a.cost < b.cost;
}


int cautare_tata(int nod)
{///cautam nodul sursa ,nu tatal direct
    while( tata[nod] != nod)
        nod =  tata[nod];

    return nod;
}

void unire_arbori(int x, int y)
{  ///intodeauna unim arborele mai mic cu cel mare

    if(rang[x] < rang[y])
         tata[x] = y;
    else
        if(rang[y] < rang[x])
           tata[y] = x;
        else
            if(rang[x] == rang[y])
            {
                 tata[x]=y;
                 rang[y]++;
            }
}

void APM()
{
    for(int i=1;i<=m;i++)
    {
    int tata_x=cautare_tata(muchia[i].x);
    int tata_y=cautare_tata(muchia[i].y);

        if(tata_x!= tata_y) ///daca nu au acs tata ii putem face pereche(nu se formeaza un ciclu)
        {
            unire_arbori(tata_x, tata_y);
            poz++;
            arbore[poz].st=muchia[i].x;
            arbore[poz].dr=muchia[i].y;
            cost_total+= muchia[i].cost;
        }
    }
}

int main()
{fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> muchia[i].x >> muchia[i].y >> muchia[i].cost;

    sort(muchia+1, muchia+m+1,  compara_costuri);

    for(int i = 1; i <= m; i++)
    {
         tata[i]=i;
         rang[i]=1;
    }

    APM();

    cout <<cost_total<<"\n"<<n-1<<"\n";

    for(int i = 1; i <= poz; i++)
        cout << arbore[i].st << " " << arbore[i].dr << "\n";

    return 0;
}