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

using namespace std;

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

const int SIZE = 400001;

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

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

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

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 << n - 1 << "\n";
    for (int i = 0; i < vec.size(); i++)
    {
        g << vec[i].first << " " << vec[i].second << "\n";
    }
}

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

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

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

void Union(int x, int y)
{
    int rootX = Find(x);
    int rootY = Find(y);
    if (rootX == rootY)
    {
        return;
    }
    parent[rootX] = rootY;
}

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

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