#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge
{    
    Edge(int x, int y, int w)
        : x{x}
        , y{y}
        , w{w}
    {}
    
    bool operator<(const Edge& that) const
    {
        return w < that.w;
    }
    
    int x, y, w;
};

using VE = vector<Edge>;
using VI = vector<int>;

int n, m, cost;
VE G, apm;
VI parent, height;

void Read();
void Kruskal();
int Find(int x);
void Union(int x, int y);
void Write();

int main()
{
    Read();
    Kruskal();
    Write();
}

void Read()
{
    ifstream fin("apm.in");
    fin >> n >> m;
    
    int x, y, w;
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> w;
        G.emplace_back(x, y, w);
    }
    
    fin.close();
}

void Kruskal()
{
    cost = 0;
    parent = height = VI(n + 1);
    for (int x = 1; x <= n; ++x)
        parent[x] = x;
    
    sort(G.begin(), G.end());
    int c1, c2;
    for (const Edge& edge: G)
    {
        c1 = Find(edge.x);
        c2 = Find(edge.y);
        if (c1 == c2)
            continue;
        
        Union(c1, c2);
        cost += edge.w;
        apm.push_back(edge);
        if (apm.size() == n - 1)
            break;
    }
}

int Find(int x)
{
    if (parent[x] == x)
        return x;
    
    return parent[x] = Find(parent[x]);
}

void Union(int x, int y)
{
    if (height[x] < height[y])
    {
        parent[x] = y;
        return;
    }
    
    parent[y] = x;
    if (height[x] == height[y])
        height[x]++;
}

void Write()
{
    ofstream fout("apm.out");
    fout << cost << '\n' << n - 1 << '\n';
    for (const Edge& edge: apm)
        fout << edge.x << ' ' << edge.y << '\n';
    
    fout.close();
}