#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const char cFile[] = "";

typedef struct _edge
{
    int v;
    int weight;
}   edge_t;

typedef struct info_
{
    int node;
    int value;
}   info_t;

void exchange(int& a, int& b)
{
    int aux = a;
    a = b;
    b = aux;
}

typedef vector<edge_t> GRAPH;

class mycompare
{
    public:
        bool operator() (const info_t& one, const info_t& two)
        {
             if(one.value < two.value)
                return true;
        return false;
        }
};


int read_graph(GRAPH*, int, fstream&);
int print_graph(GRAPH*, int, char*);

int extract_min(int* key, bool* belong, int size)
{
    int min = INT_MAX;
    int min_key = -1;
    for(int i = 0; i < size; i++)
    {
        if( key[i] < min && belong[i] == true)
        {
            min_key = i;
            min = key[i];
        }
    }
    
return min_key;
}

int MST_Prim(GRAPH* g, int size, int source, fstream& o)
{
    int parent[size];
    int key[size];
    bool belong[size];
    
    int _u,_v;
    int sum = 0;
    // initialization
    for(int i = 0 ; i < size; i++)
    {
        parent[i] = -1;
        key[i] = INT_MAX;
        belong[i] = true;
        
    }

    key[source] = 0;
    GRAPH::iterator it;
    
    for( int i = 0; i < size; i++)
    {
        _u = extract_min(key, belong, size);
        //cout << "\n\t" << _u;
        for( it = g[_u].begin(); it != g[_u].end(); it++)
        {
            _v = (*it).v;
            if( belong[_v] == true && (*it).weight < key[_v])
            {
                key[_v] = (*it).weight;
                parent[_v] = _u;
                
                
            }
        }
        belong[_u] = false;
    }
    
    for(int i = 0; i < size; i++)
        sum += key[i];
        o << sum << endl;
        o << size-1 << endl;
    for(int i = 1; i < size; i++)
    {
        o << parent[i]+1 << " " << i+1 << endl;
    }
    
return 0;
}

/*
    M A I N
*/
int main(void)
{
    fstream fhandle( "input/apm.in", fstream::in);
    fstream out( "input/apm.out", fstream::out);
    
    if( !fhandle.is_open() )
    {
        cerr << "! Nu am deschis fisier !";
        return -1;
    }
    int nVertices, nEdges;
    fhandle >> nVertices >> nEdges;

GRAPH adj_list[nVertices];

read_graph(adj_list, nEdges, fhandle);
//print_graph(adj_list, nVertices, " - Lista de adiacenta si ponderea fiecarei muchii.");


    MST_Prim(adj_list, nVertices, 0, out);
    
    fhandle.close();
    out.close();
return 0;
}

int read_graph(GRAPH* g, int size, fstream& fh)
{
    int _u;
    edge_t temp;
    
    for(int i = 0; i < size; i++)
    {
        fh >> _u;
        fh >> temp.v;
        fh >> temp.weight;
        
        temp.v -= 1;
        _u -= 1;
        g[_u].push_back(temp);
        exchange(temp.v, _u);
        g[_u].push_back(temp);
    }
    
return 0;
}

//
int print_graph(GRAPH* g, int size, char* output)
{
    GRAPH::iterator it;

    cout << endl << output;
    for(int i = 0; i < size; i++)
    {
        for( it = g[i].begin(); it != g[i].end(); it++)
        {
            cout << "\n -> (" << i << "," << (*it).v << "): " << (*it).weight << ";";
        }
    }
    
return 0;
}