/**************************************************\
*
*   Algoritmul lui Kruskal pentru determinarea
* arborelui partial de cost minim cu Priority Queue
*
***************************************************/

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

using std::vector;
using std::cout;
using std::cin;
using std::ifstream;
using std::ofstream;
using std::priority_queue;
using std::swap;
using std::endl;

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

struct edges
{
    int a,  // nodul de plecare
        b,  // nodul de sosire
        c;  // costul asociat
};

vector <edges> graph[400005],finalVersion;
priority_queue <edges> mainQueue;
vector <bool> visited;

int n,  // Noduri [1,200000]
    m,  // Muchii [1,400000]
    u,  // citire nod plecare
    v,  // citire nod sosire
 cost;  // citire nod asociat

long long int totalCost; // Cost [-1000,1000]
edges aux;


bool operator<(const edges &a, const edges &b) {return a.c>b.c;} // pentru priority queue si swap

void setAux(int u, int v, int cost)
{
    aux.a=u;
    aux.b=v;
    aux.c=cost;
}

void read()
{
    fin >> n >> m;
    visited.resize(n,false);

    for(int i=0;i<m;i++)
    {
        fin >> u >> v >> cost;
        setAux(u,v,cost);
        graph[u].push_back(aux);
        swap(aux.a,aux.b);
        graph[v].push_back(aux);
    }
}

void kruskalAlgorithm(int vertex)
{
    edges currentNode;
    currentNode.a = currentNode.b = vertex, currentNode.c = 0;
    mainQueue.push(currentNode);

    while(!mainQueue.empty())
    {
        currentNode = mainQueue.top(); mainQueue.pop();
        if(!visited[currentNode.b])
        {
            for(unsigned int i=0;i<graph[currentNode.b].size();i++)
                if(!visited[graph[currentNode.b][i].b])
                    mainQueue.push(graph[currentNode.b][i]);
            visited[currentNode.b]=true;
            totalCost += currentNode.c;
            finalVersion.push_back(currentNode);
        }
    }
}

void print()
{
    cout << totalCost << endl;
    cout << finalVersion.size()-1 << endl;
    for(unsigned int i=1;i<finalVersion.size();i++)
        cout << finalVersion[i].a << " " << finalVersion[i].b << endl;

}

int main()
{
    read();
    kruskalAlgorithm(1);
    print();

    return 0;
}