/*
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;
}