#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 <pairNodes> ShowEdges;
vector <pairCosts> graph;
int numberOfNodes, numberOfEdges;
long long int 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];
}

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

void link(unsigned int vertex1, unsigned int vertex2)
{
    parent[root(vertex1)] = parent[vertex2];
}

bool cmp(pairCosts a, pairCosts b)
{
    return a.first<b.first;
}

void kruskal_algorithm()
{
    sort(graph.begin(),graph.end(),cmp);
    totalCost=0;
    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;
        }
    }
}

void print()
{
    h << totalCost << endl;
    h << ShowEdges.size() << endl;

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

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

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


    kruskal_algorithm();
    print();
    return 0;
}