#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
struct elem{
    int x, y, cost;
};
elem v[200200];
inline bool cmp(elem a, elem b)
{
    return a.cost < b.cost;
}
int dim[200200];
int tata[200200];

int tata_multime(int x)
{
    if(x != tata[x])
    {
        return tata_multime(tata[x]);
    }
    return tata[x];
}

void unire(int x, int y)
{
    x = tata_multime(x);
    y = tata_multime(y);
    if(x != y)
    {
        if(dim[x] >= dim[y])
        {
            dim[x] += dim[y];
            tata[y] = x;
        }
        else
        {
            dim[y] += dim[x];
            tata[x] = y;
        }
    }
}

vector<pair<int,int>> perechi;

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        dim[i] = 1;
        tata[i] = i;
    }
    for(int i = 1; i <= m; i ++)
    {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }
    int ans = 0;
    sort(v + 1, v + m + 1, cmp);
    for(int i = 1; i <= m; i ++)
    {
        int x = v[i].x, y = v[i].y;
        if(tata_multime(x) != tata_multime(y))
        {
            unire(x, y);
            ans += v[i].cost;
            perechi.push_back(make_pair(x, y));
        }
    }
    fout << ans << '\n';
    fout << perechi.size() << '\n';
    for(auto it : perechi)
    {
        fout << it.first << ' ' << it.second << '\n';
    }
    return 0;
}