#include <bits/stdc++.h>

using namespace std;

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

int n, m, tt[200001], rg[200001], k, Suma;

struct Muchie{
    int x, y, cost;

}V[200001], Sol[400002];

void Citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> V[i].x >> V[i].y >> V[i].cost;
    }
}

void pregatireVectorTati()
{
    for(int i = 1; i <= n; i++)
    {
        tt[i] = i;
        rg[i] = 1;
    }
}

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

void Sortare()
{
    sort(V+1, V+m+1, Compare);
}

int Find(int Nod)
{
    while(tt[Nod] != Nod)
        Nod = tt[Nod];
    return Nod;

}

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

void APM()
{
    for(int i = 1; i <= m; i++)
    {
        int tt_x = Find(V[i].x), tt_y = Find(V[i].y);
        if(tt_x != tt_y)
        {
            Unire(tt_x, tt_y);
            k++;
            Sol[k].x = V[i].x;
            Sol[k].y = V[i].y;
            Suma += V[i].cost;
        }

    }
}

int main()
{
    Citire();
    pregatireVectorTati();
    Sortare();
    APM();

    fout << Suma << endl << n-1 << endl;
    for(int i = 1; i <= k; i++)
    {
        fout << Sol[i].x << " " << Sol[i].y <<endl;
    }

    return 0;
}