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

using namespace std;

ifstream f("apcm.in");
ofstream g("apcm.out");

int n, m, cost;

class Edge  // muchie
{
public:
    int source, destination, weight;
}edges[10000];


class Subset    // exista un lant intre toate elementele dintr-un subset
{
public:
    int parent, rank;
};


bool cmp(Edge x, Edge y)    // comparam in functie de valoarea muchiei
{
    return x.weight < y.weight;
}


void Read() // citire date graf
{
    int i;
    f>>n>>m;
    for(i = 0; i < m; i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        edges[i].source = x;
        edges[i].destination = y;
        edges[i].weight = z;
    }
}

/*
void PrintEdges()   // print graf initial
{
    int i;
    cout<<"======= GRAF =======\n";
    for(i = 0; i < m; i++)
        cout<<edges[i].source<<" "<<edges[i].destination<<" "<<edges[i].weight<<'\n';
}
*/

int Find(Subset subsets[], int i)
{
    if(subsets[i].parent != i)  // diferit de valoarea initiala
        subsets[i].parent = Find(subsets, subsets[i].parent);    // path compression

    return subsets[i].parent;
}

void Union(Subset subsets[], int x, int y)
{
    int xSet = Find(subsets, x);
    int ySet = Find(subsets, y);

    if(subsets[xSet].rank < subsets[ySet].rank)     // nodul cu rank mai mic
        subsets[xSet].parent = ySet;                // devine copilul nodului cu rank mai amre
    else if (subsets[xSet].rank > subsets[ySet].rank)
        subsets[ySet].parent = xSet;
    else                                            // daca rank-urile sunt egale
    {                                               // un nod va deveni parintele celulalt, rank-ul lui crescand cu 1
        subsets[ySet].parent = xSet;
        subsets[xSet].rank++;
    }
}

void Kruskal(Edge edges[])
{
    int count = 0, nr = 0;
    Edge result[1000];
    Subset subsets[1000];

    sort(edges, edges + m, cmp);
    for(int i = 0; i < n; i++)
    {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }

    while(count < n - 1 && nr < m)
    {
        Edge next = edges[nr++];
        int x = Find(subsets, next.source);
        int y = Find(subsets, next.destination);

        if(x != y)
        {
            result[count++] = next;
            Union(subsets, x, y);
        }
    }

    //cout<<"======= APM =======\n";

    for(int i = 0; i < count; i++)
    {
        //cout<<result[i].source<<" "<<result[i].destination<<" -> "<<result[i].weight<<'\n';
        cost += result[i].weight;
    }
    g<<cost<<'\n';
    g<<count<<'\n';

    for(int i = 0; i < count; i++)
        g<<result[i].source<<" "<<result[i].destination<<'\n';


}

int main()

{
    Read();

    Kruskal(edges);



    return 0;
}