#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, totalCost;

class kruskal
{
public:
    unsigned int rang[MAX],parent[MAX];

    kruskal(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()
{
    kruskal object(numberOfNodes);
    unsigned int u,v;
    for(int i=0;i<numberOfEdges;i++)
    {
        u = graph[i].second.first;
        v = graph[i].second.second;
        if(!object.findCommonRoot(u,v))
        {
            ShowEdges.push_back(make_pair(u+1,v+1));
            object.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++)
    {
        pair<int,int> aux;
        aux = ShowEdges[i];
        h << aux.first << " " << aux.second << endl;
    }


}