/*
Se da un graf neorientat G=(V,E) cu costuri pe muchii
Gasiti un arbore partial de cost minim al sau folosinf algoritmul lui Kruskal
*/

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

using namespace std;

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

struct muchie {int i, j, c; };

vector < muchie > V, K;
bool pus[200001];
int n, m, T[200001], H[200001], nrm, c;

int CMP(muchie a, muchie b)
{
    return a.c < b.c;
}

int Tata(int nod)
{
    while(T[nod])
        nod = T[nod];
    return nod;
}

void Read()
{
    fin >> n >> m;
    muchie x;

    for(int i = 1; i <= m; i++)
    {
        fin >> x.i >> x.j >> x.c;
        V.push_back(x);
    }
    sort(V.begin(), V.end(), CMP);
}

void Add(muchie x)
{
    int v1 = Tata(x.i), v2 = Tata(x.j);

    if(v1 == v2)
        return;

    nrm++, K.push_back(x), c += x.c;

    if(H[v1] == H[v2])
    {
        T[v1] = v2;
        H[v2]++;
    }
    else
    {
        if(H[v1] < H[v2])
            T[v1] = v2;
        else
            T[v2] = v1;
    }

}

void Kruskal()
{

    for(int i = 0; nrm < n && i < V.size(); i++)
        Add(V[i]);
}

int main()
{
    Read();
    Kruskal();

    fout << c << "\n" << nrm << "\n";

    for(int i = 0; i < K.size(); i++)
        fout << K[i].i << " " << K[i].j << "\n";

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