#include<fstream>
#include<vector>
#include<algorithm>
#define NMAX 200005
#define MMAX 500005
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct x2
{
    int x;
    int y;
    int z;
};
x2 mch[MMAX];
vector<pair<int, int> > sol1;
int n, m, nn, sol0, i;
int up_nod, rx, ry, n_mch;
int t[NMAX];
void init()
{
    for(int nod = 1; nod <= n; nod++)
    {
        t[nod] = -1;
    }
}
int rad(int nod)
{
    while(t[nod] > 0)
    {
        nod = t[nod];
    }
    return nod;
}
void compresie(int nod, int root)
{
    while(nod != root)
    {
        up_nod = t[nod];
        t[nod] = root;
        nod = up_nod;
    }
}
bool unite(int x, int y)
{
    rx = rad(x);
    ry = rad(y);
    if(rx != ry)
    {
        n_mch++;
        if(t[rx] > t[ry])
        {
            swap(rx, ry);
        }
        t[rx] += t[ry];
        t[ry] = rx;
        compresie(y, rx);
    }else
    {
        return 0;
    }
}
bool cmp(x2 a, x2 b)
{
    return a.z < b.z;
}
void afisare()
{
    cout << sol0 << "\n";
    cout << sol1.size() << "\n";
    for(int i = 0; i < sol1.size(); i++)
    {
        cout << sol1[i].first << " " << sol1[i].second << "\n";
    }
}
int main()
{
    init();
    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> mch[i].x >> mch[i].y >> mch[i].z;
    }
    sort(mch + 1, mch + m + 1, cmp);

    for(i = 1; i <= m && n_mch < n - 1; i++)
    {
        if(unite(mch[i].x, mch[i].y))
        {
            sol0 += mch[i].z;
            sol1.push_back(make_pair(mch[i].x, mch[i].y));
        }
    }
    afisare();
}