#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

ifstream f("apm.in");
ofstream h("apm.out");

#define pairNodes pair<int,int>
#define pairCosts pair<int,pairNodes>
#define MAX 200005

vector <pair <int,int> > ShowEdges;
vector <pairCosts> graph;
int numberOfNodes, numberOfEdges, totalCost;

unsigned int rang[MAX],parent[MAX];

void initializer(int numberOfVertex=0)
{
    for(int i=0; i<numberOfVertex; i++)
    {
        rang[i]=0;
        parent[i]=i;
    }
}

int root(unsigned int vertex)
{
    if(parent[vertex]==vertex) return vertex;
    parent[vertex] = root(parent[vertex]);
    return parent[vertex];
}

int findCommonRoot(unsigned int vertex1, unsigned int vertex2)
{
    return root(vertex1)==root(vertex2);
}

void link(unsigned int vertex1, unsigned int vertex2)
{
    unsigned int root1,root2;
    root1 = root(vertex1);
    root2 = root(vertex2);

    if(rang[root1]<rang[root2])
    {
        parent[root1]=root2;
        rang[root2]+=rang[root1];
    }
    else
    {
        parent[root2]=root1;
        rang[root1]+=rang[root2];
    }
}


void kruskal_algorithm()
{
    initializer(numberOfEdges);
    unsigned int u,v;
    for(int i=0; i<numberOfEdges; i++)
    {
        u = graph[i].second.first;
        v = graph[i].second.second;
        if(!findCommonRoot(u,v))
        {
            ShowEdges.push_back(make_pair(u+1,v+1));
            link(u,v);
            totalCost += graph[i].first;
        }
    }
}

int main()
{
    int u,v,costUV;

    f >> numberOfNodes >> numberOfEdges;
    graph.resize(numberOfEdges);
    for(unsigned int i=0; i<(unsigned)numberOfEdges; i++)
    {
        f >> u >> v >> costUV;
        u--;
        v--;
        graph[i] = pairCosts(costUV,pairNodes(u,v));
    }
    sort(graph.begin(),graph.end());

    kruskal_algorithm();

    h << totalCost << endl;
    h << ShowEdges.size() << endl;
    for(unsigned int i=0; i<(unsigned)numberOfNodes-1; i++)
    {
        h << ShowEdges[i].first << " " << ShowEdges[i].second << endl;
    }
}