#include <fstream>
#include <algorithm>
#include <vector>
#define MAX_SIZE 400000


using namespace std;

typedef struct muchie
{
    int start;
    int finish;
    int cost;
};

muchie graf[MAX_SIZE];
int tree[MAX_SIZE >> 1];
vector <muchie> vect;

int N , M;

bool cmp(muchie a , muchie b)
{
    return a.cost < b.cost;
}


int get_root(int nod)
{
    int radacina = nod;
    while (tree[radacina] != radacina)
    {
        radacina = tree[radacina];
    }

    int x = nod;
    while ( tree[x] != x)
    {
        int aux = tree[x];
        tree[x] = radacina;
        x = aux;
    }

    return radacina;
}


int main()
{
    ifstream input("apm.in");
    ofstream output("apm.out");
    input >> N >> M;
    for (int i =0;i<M;i++)
    {
        input >> graf[i].start >> graf[i].finish >> graf[i].cost;
    }
    for (int i =1;i<=N;i++)
    {
        tree[i] = i;
    }
    sort(graf,graf + M , cmp);
    int cost_total = 0;
    for (int i =0;i<M;i++)
    {
        if (get_root(graf[i].start) != get_root(graf[i].finish))
        {
            vect.push_back(graf[i]);
            tree[get_root(graf[i].start)] = get_root(graf[i].finish);
            cost_total += graf[i].cost;
        }
    }

    output << cost_total << "\n" << vect.size();

    for (int i =0;i<vect.size();i++)
    {
        output << "\n" << vect[i].finish << " " << vect[i].start;
    }


    return 0;
}