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

using namespace std;

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

const int SIZE = 200005;

int n, m, cnt, mstCost;
int parent[SIZE], rang[SIZE];

vector <tuple <int, int, int> > edges;
vector <pair <int, int> > ans;

void Read()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        f >> x >> y >> z;
        edges.push_back(make_tuple(x, y, z));
    }
}

inline bool Compare(tuple <int, int, int> x,
                    tuple <int, int, int> y)
{
    return get<2>(x) < get<2>(y);
}

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

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

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

void Solve()
{
    sort(edges.begin(), edges.end(), Compare);
    MakeSet();

    for (unsigned int i = 0; i < edges.size() && cnt < n - 1; i++)
    {
        int x, y, z;
        tie(x, y, z) = edges[i];

        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY)
        {
            Union(rootX, rootY);
            ans.push_back(make_pair(x, y));
            mstCost += z;
            cnt++;
        }
    }
}

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

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}