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

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[450000],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 int totalCost; // Cost [-1000,1000]
edges aux;


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

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

void Swap()
{
    int x;
    x = aux.a;
    aux.a =aux.b;
    aux.b = x;
}

void read()
{
    fin >> n >> m;
    visited.resize(n,false);
    totalCost=0;
    for(int i=0;i<m;i++)
    {
        fin >> u >> v >> cost;
        setAux(u,v,cost);
        graph[u].push_back(aux);
        Swap();
        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()
{
    fout << totalCost << endl;
    fout << finalVersion.size()-1 << endl;
    for(unsigned int i=1;i<finalVersion.size();i++)
        fout << finalVersion[i].a << " " << finalVersion[i].b << endl;
}

int main()
{
    read();
    kruskalAlgorithm(1);
    print();
    return 0;
}