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


using namespace std;




typedef struct _edge
{
    bool ok;
    int  u, v, weight;
} edge_t;



int read_graph(vector<edge_t>& v, int size, fstream& f)
{
    
    edge_t temp;
    int _u, _v, w;

        for(int i = 0; i < size; i++)
        {
                f >> _u; // completez cu nodurile pentru care (i,j) = adiacente
                f >> _v;
                f >> w;
    
                temp.ok = false;
                temp.u = _u-1;
                temp.v = _v-1;
                temp.weight = w;
                v.push_back(temp);
                
        }
        

return 0;
}


int print_graph(vector<edge_t>& g)
{
    vector<edge_t>:: iterator it;
    cout << "Ponderile muchiilor: " << endl;
    
    for(it = g.begin(); it != g.end(); it++)
            cout << "(" << (*it).u << "," << (*it).v << "): " << (*it).weight << endl;
        cout << endl;
        
return 0;
}

/*
    Functie de comparare pentru 2 valori  edge_t
*/
bool myCompare(const edge_t& a, const edge_t& b)
{
    return a.weight < b.weight;
}


int MST_Kruskal(vector < edge_t > G, const int& uiSize, fstream& out)
{
    int myset[uiSize];
    
    int Sum = 0;
    int _u,_v;
    vector<edge_t>:: iterator it;
    vector<edge_t> temp;
/*
    Make set !
*/
    for(int i = 0; i < uiSize; i++)
    {
        myset[i] = i;
    }
    
    for( it = G.begin(); it != G.end(); it++)
    {
        _u = (*it).u;
        _v = (*it).v;
            
            if( myset[_u] != myset[_v] )
            {
                Sum += (*it).weight;
                
                (*it).ok = true;
                
                
                int k = myset[_u];
                int l = myset[_v];
                for (int j = 0; j < uiSize; j++)
                {
                    if(myset[j] == k)
                        myset[j] = l;
                }
                
            }
            /*
            cout << endl << endl << " -   Pentru muchia -> " << (*it).weight << " <- vect  'myset' este: " << endl;
            for(int i=0 ; i< uiSize; i++)
            {
                cout << "  " << myset[i];
            }*/
    }
    
    out << Sum << endl;
    out << uiSize - 1 << endl;    
    for( it = G.begin(); it != G.end(); it++)
        if((*it).ok)
        {
            out << (*it).u+1 << " " << (*it).v+1 << endl;
        }


return Sum;
}   // 0 on success


int main()
{
/*  
    File stream for graph nodes;
*/
fstream fhandle( "apm.in", fstream::in);
fstream out( "apm.out", fstream::out);

if(! fhandle.good() )
{
    cerr << "Nu am putut deschide fisierul!" << endl;
    return -1;
}

int uiSize = 0;
int nEdges;
fhandle >> uiSize;  // |V(G)|
fhandle >> nEdges;


vector<edge_t> edge_v;  // Graful reprezentat printr-un vector al muchiilor


read_graph(edge_v, nEdges, fhandle); // citesc graful
//cout << "\n\n";
//print_graph(edge_v);    // afisare

sort( edge_v.begin(), edge_v.end(), myCompare); // sortare in ordine crescatoare
                                                // a muchiilor

//cout << endl;
//print_graph(edge_v);    // afisare

int Sum = MST_Kruskal(edge_v, uiSize, out);

//cout << endl << "MST is: " << Sum;

fhandle.close();
out.close();
return 0;
}