#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, countedEdges;
int parent[SIZE], Rang[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 << countedEdges << "\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 k)
{
    if(parent[k] == k)
    {
        return k;
    }
    else
    {
        int x = Find(parent[k]);
        parent[k] = x;
        return x;
    }
}

void Union(int x, int y)
{
    int rk = Find(x), rp = Find(y);
    if(rk != rp)
    {
        if(Rang[rk] > Rang[rp])
            parent[rp] = rk;
        else
        {
            parent[rk] = rp;
            if(Rang[rk] == Rang[rp])
                Rang[rp] ++;
        }
    }
}

void Kruskal()
{
    for (int i = 1; i <= m && countedEdges <= n-1; 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));
            countedEdges++;
        }
    }
}

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