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

using namespace std;

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

const int N_MAX = 200001;
const int M_MAX = 400001;

struct Edge
{
    int from, to, cost;
}edges[M_MAX];

int n, m, mstCost;
int father[N_MAX], rang[N_MAX];

vector <pair <int, int> > added;

bool Compare(Edge a, Edge b)
{
    return a.cost < b.cost;
}

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

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

void Union(int x, int y, int cost)
{
    int rootX = Find(x);
    int rootY = Find(y);

    if (rootX != rootY)
    {
        mstCost += cost;
        added.push_back(make_pair(x, y));

        if (rang[rootX] > rang[rootY])
        {
            father[rootY] = rootX;
        }
        else
        {
            father[rootX] = rootY;
            if (rang[rootX] == rang[rootY])
            {
                rang[rootY]++;
            }
        }
    }
}

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

int main()
{
    Read();
    sort(edges + 1, edges + m + 1, Compare);

    for (int i = 1; i <= m; i++)
    {
        Union(edges[i].from, edges[i].to, edges[i].cost);
    }

    Print();
}