#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <forward_list>

using namespace std;

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

class DisjointSets
{
public:
    vector<int> father, size_;

    DisjointSets();
    DisjointSets(int n);
    void unite(int x, int y);
    int find(int x);
    void resize(int n);
};
class Edge
{
public:
    int x, y, cost;
};

int main()
{
    DisjointSets subtrees;
    int nodeCount, edgeCount, minCost = 0, selectedSize = 0;
    vector<Edge> edges;
    forward_list<Edge> selected;

    fin >> nodeCount >> edgeCount;
    edges.resize(edgeCount);
    subtrees.resize(nodeCount + 1);
    
    for(int i = 0, x, y, cost; i < edgeCount; i++)
    {
        fin >> x >> y >> cost;

        edges[i].x = x;
        edges[i].y = y;
        edges[i].cost = cost;
    }

    sort(edges.begin(), edges.end(), [](Edge& a, Edge& b){return a.cost < b.cost;});

    for(int i = 0; i < edges.size(); i++)
    {   
        int xRep, yRep;
        xRep = subtrees.find(edges[i].x);
        yRep = subtrees.find(edges[i].y);

        if(xRep == yRep)
            continue;
        
        subtrees.unite(xRep, yRep);
        minCost += edges[i].cost;
        selected.push_front(edges[i]);
        selectedSize++;
    }

    fout << minCost << '\n' << selectedSize << '\n';

    for(auto& e : selected)
    {
        fout << e.x << ' ' << e.y << '\n';
    }

    return 0;
}

DisjointSets::DisjointSets()
{

}
DisjointSets::DisjointSets(int n)
{
    this->resize(n);
}
void DisjointSets::unite(int x, int y)
{
    int xRep, yRep;

    xRep = this->find(x);
    yRep = this->find(y);

    if(this->size_[xRep] < this->size_[yRep])
    {
        this->size_[yRep] += this->size_[xRep];
        this->father[xRep] = yRep;
    }
    else
    {
        this->size_[xRep] += this->size_[yRep];
        this->father[yRep] = xRep;
    }
}
int DisjointSets::find(int x)
{
    if(this->father[x] == -1)
        return x;
    
    int rep = this->find(this->father[x]);
    this->father[x] = rep;

    return rep;
}
void DisjointSets::resize(int n)
{
    this->father = vector<int>(n, -1);
    this->size_ = vector<int>(n, 1);
}