#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;
int parent[SIZE], rang[SIZE];

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

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

void MakeSet(int n)
{
    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 Read()
{
    f >> n >> m;

    MakeSet(n);

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

void Solve()
{
    int cnt = 0, mstCost = 0;
    vector < pair <int, int> > ans;

    sort(edges.begin(), edges.end(), Compare);
    for (unsigned int i = 0; i < edges.size() && cnt < n - 1; i++)
    {
        int x = get<0>(edges[i]);
        int y = get<1>(edges[i]);
        int cost = get<2>(edges[i]);

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

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

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

    return 0;
}