#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define MAXN 200005
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct edge
{
    int firstVertex, secondVertex;
    double cost;
    bool operator < (const edge &other) const
    {
        return (cost<other.cost);
    }
};

vector<edge> Edges, solution;
int numberEdges, numberVertices;
int numberTree[MAXN];
double minimumTreeCost=0;
void sortEdges()
{
    sort(Edges.begin(),Edges.end());
}

void initializeVector()
{
    for(int i=1;i<=numberVertices;++i)
        numberTree[i]=i;
}
void joinTrees(int firstTree, int secondTree)
{
    for(int i=1;i<=numberVertices;++i)
        if(numberTree[i]==secondTree)
            numberTree[i]=firstTree;
}
void printSolution()
{
    fout<<minimumTreeCost<<"\n";
    fout<<numberVertices-1<<"\n";
    for(auto &e:solution)
        fout<<e.firstVertex<<" "<<e.secondVertex<<"\n";
}
void solve()
{
    int chosenEdges=0;
    for(auto &e:Edges)
        if(numberTree[e.firstVertex]!=numberTree[e.secondVertex])
        {
            joinTrees(numberTree[e.firstVertex], numberTree[e.secondVertex]);
            minimumTreeCost+=e.cost;
            solution.push_back(e);
            ++chosenEdges;
            if(chosenEdges==numberVertices-1)
                break;
        }
}
void read()
{
    fin>>numberVertices>>numberEdges;
    int i,j,c;
    for(int q=0;q<numberEdges;++q)
        fin>>i>>j>>c, Edges.push_back({i,j,c});
    initializeVector();
    sortEdges();
    solve();
    printSolution();
}
int main()
{
    read();
    return 0;
}