#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 4e5;

struct str{
    int first, second, cost;
};

int n, m;
str muchii[NMAX+1];
int t[NMAX+1];
vector < pair<int,int> > ans;

int Radacina(int nod)
{
    if(t[nod] == 0)
        return nod;
    return t[nod] = Radacina(t[nod]);
}

void Union(int x, int y)
{
    t[y] = x;
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
        fin >> muchii[i].first >> muchii[i].second >> muchii[i].cost;
    sort(muchii+1,muchii+1+m, [](str A, str B){return A.cost < B.cost;});
    int S = 0;
    for(int i=1; i<=m; i++)
    {
        int r1 = Radacina(muchii[i].first);
        int r2 = Radacina(muchii[i].second);
        if(r1 != r2)
        {
            ans.push_back(make_pair(muchii[i].first, muchii[i].second));
            S+=muchii[i].cost;
            Union(r1, r2);
        }
    }
    fout << S << '\n' << ans.size() << '\n';
    for(auto a : ans)
        fout << a.first << ' ' << a.second << '\n';
    return 0;
}