#include <iostream>
#include <fstream>
#include <queue>
#include <sys/time.h>
#include <vector>

using std::ifstream;
using std::ofstream;
using std::cout;
using std::vector;
using std::priority_queue;
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
}aux;

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


int n,  // Noduri [1,200000]
    m;  // Muchii [1,400000]

int totalCost; // Cost [-1000,1000]

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

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 = totalCost + currentNode.c;
            finalVersion.push_back(currentNode);
        }
    }
}

void Swap(edges &ed)
{
    int x;
    x = ed.a;
    ed.a=ed.b;
    ed.b=x;
}

int main()
{

    fin >> n >> m;
    int u,v,cost;
    totalCost=0;
    for(int i=m;i--;)
    {
        fin >> u >> v >> cost;
        aux.a = u, aux.b = v;
        aux.c = cost;
        graph[u].push_back(aux);
        Swap(aux);
        graph[v].push_back(aux);
    }
    visited.resize(n+10,false);

    kruskalAlgorithm(1);

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

    return 0;
}