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

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

struct muchie
{
    int c,x,y;
};
int n,m,k,s;

muchie M[400001];
muchie A[200000];
int T[200001];
bool ord(muchie x, muchie y)
{
    return (x.c<y.c);
}

void read ()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        fin>>M[i].x>>M[i].y>>M[i].c;
    }
    sort(M,M+m,ord);
}
int get_root(int node)
{
    int aux = node;
    while (T[node] > 0)
        node = T[node];
    int root = node;
    // mai parcurg odata acelasi drum si unesc nodurile de root
    node = aux;
    while (node != root)
    {
        aux = T[node];
        T[node] = root;
        node = aux;
    }
    return root;
}
void join(int x, int y)
{
    int root_x = get_root(x);  // radacina arborelui lui x
    int root_y = get_root(y);  // radacina arborelui lui y
    if (root_x == root_y)  // sunt deja in acelasi arbore
        return;
    if (T[root_x] <= T[root_y])    // arborele lui x are mai multe noduri
    {
        T[root_x] += T[root_y];
        T[root_y] = root_x;  // legam arborele lui y de arborele lui x
    }
    else
    {
        T[root_y] += T[root_x];
        T[root_x] = root_y;  // legam arborele lui x de arborele lui y
    }
}
bool query(int x, int y)
{
    // x si y sunt in acelasi arbore daca au aceeasi radacina
    return get_root(x) == get_root(y);
}

void kruskal()
{
    int i, uRep, vRep;
    // increasing weight
    for (i = 0; i < m; i++)
    {

        if (get_root(M[i].x) != get_root(M[i].y))
        {
            join(M[i].x,M[i].y);  // add to tree
            A[k++]=M[i];
            s+=M[i].c;
        }
    }
}
void print(muchie a[], int m)
{
    fout<<s<<endl;
    fout<<k<<endl;
    for (int i = 0; i < m; i++)
    {
        fout << a[i].x << " " << a[i].y<< endl;
    }
}
int main()
{
    read();
    kruskal();
    print(A,k);
    return 0;
}