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

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

const int SIZE = 400001;

struct Vertex
{
    int at, to, cost;
}V[SIZE];

int n, m, mstCost, countedEdges;
int parent[SIZE], Rank[SIZE];
vector <pair <int, int>> vec;

bool CompareCost(Vertex x, Vertex y)
{
    return x.cost < y.cost;
}

void SortVertices()
{
    sort(V+1, V+m+1, CompareCost);
}

void MakeSet()
{
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
    }
}

void Read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> V[i].at >> V[i].to >> V[i].cost;
    }
}

void Print()
{
    g << mstCost << "\n";
    g << countedEdges << "\n";
    for (int i = 0; i < vec.size(); i++)
    {
        g << vec[i].first << " " << vec[i].second << "\n";
    }
}

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

void Union(int x, int y, int rootX, int rootY)
{
    if (Rank[rootX] > Rank[rootY])
    {
        parent[rootY] = rootX;
    }
    else
    {
        parent[rootX] = rootY;
        if (Rank[rootX] == Rank[rootY])
        {
            Rank[rootX]++;
        }
    }
}

void Kruskal()
{
    for (int i = 1; i <= m && countedEdges != n-1; i++)
    {
        int rootX = Find(V[i].at);
        int rootY = Find(V[i].to);
        if (rootX != rootY)
        {
            Union(V[i].at, V[i].to, rootX, rootY);
            mstCost += V[i].cost;
            vec.push_back(make_pair(V[i].at, V[i].to));
            countedEdges++;
        }
    }
}

int main()
{
    Read();
    SortVertices();
    MakeSet();
    Kruskal();
    Print();
}