#include <fstream>
#include <algorithm>
#define maxN 400000
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");

pair <int, int> Perechi[maxN];
int k = 0;
int N, M;

struct Muchie{
    int x, y, cost;
};

Muchie v[maxN];
int Tata[maxN], Rang[maxN], Total = 0;

bool Cmp (Muchie a, Muchie b)
{
    return a.cost < b.cost;
}

int Verif_tata (int Nod)
{
    while(Tata[Nod] != Nod)
        Nod = Tata[Nod];
    return Nod;
}

void Unire (int x, int y)
{
    if(Rang[x] < Rang[y]) Tata[x] = y;
    else if(Rang[x] > Rang[y]) Tata[y] = x;
    else{
        Tata[x] = y;
        Rang[y]++;
    }
}

void Kruskal()
{
    for(int i = 1; i <= M; i++)
    {
        int Tatal_x = Verif_tata(v[i].x);
        int Tatal_y = Verif_tata(v[i].y);
        if(Tatal_x != Tatal_y)
        {
            Unire(Tatal_x, Tatal_y);
            Perechi[++k].first = v[i].x;
            Perechi[k].second = v[i].y;
            Total += v[i].cost;
        }
    }
}

void Afisare()
{
    cout << Total << "\n";
    cout << N - 1 << "\n";
    for(int i = 1; i <= k; i++)
        cout << Perechi[i].first << " " << Perechi[i].second << "\n";
}

void Citire()
{
    cin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        cin >> v[i].x >> v[i].y >> v[i].cost;
        Tata[i] = i;
        Rang[i] = 1;
    }
    sort(v+1, v+M+1, Cmp);
}
int main()
{
    Citire();
    Kruskal();
    Afisare();
    return 0;

}