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

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int r[200001],l[200001];
struct vec
{
    int x ,y, c;
};
vector <vec> muchii;
vector <pair<int, int>> afis;
bool cmp(vec &a,vec &b)
{
    if (a.c < b.c)
        return true;
    return false;
}
int Find(int x)
{
    if (x != r[x])
        r[x] = Find(r[x]);
    return r[x];
}
void Union(int x, int y)
{
    int findX = Find(x);
    int findY = Find(y);
    if (l[findX] > l[findY])
        r[findY] = findX;
    else
        if (l[findX] < l[findY])
            r[findX] = findY;
        else
        {
            r[findX] = findY;
            l[findX]++;
        }
}
int main()
{
    int n, m, i, x, y, c,ctot=0;
    ;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        r[i] = i;
    for (i = 1; i <= m; i++)
    {
        cin >> x>>y>>c;
        muchii.push_back({ x,y,c });
    }
    sort(muchii.begin(), muchii.end(), cmp);

    for (i = 0; i < m; i++)
    {
        x = muchii[i].x;
        y = muchii[i].y;
        c = muchii[i].c;
        int findX = Find(x);
        int findY = Find(y);
        if (findX != findY)
        {
            Union(findX, findY);
            ctot += c;
            afis.push_back({ x,y });
        }
    }
    cout << ctot << '\n' << n - 1 << '\n';
    for (auto var : afis)
        cout << var.first << ' ' << var.second << '\n';
}