#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct muchie
{
    int a, b, c;
};

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

const int N = 200001;

int n, m, parents[N];
vector<muchie> muchii;

int gaseste(int i)
{
    if (parents[i] != i)
        parents[i] = gaseste(parents[i]);
    return parents[i];
}

void uneste(int i, int j)
{
    parents[gaseste(i)] = gaseste(j);
}

int main()
{
    fin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int x, y, z;
        fin>>x>>y>>z;
        muchii.push_back({x, y, z});
    }

    for(int i=1;i<=n;++i)
        parents[i] = i;
    sort(muchii.begin(), muchii.end(), cmp);

    int cst = 0;
    vector<pair<int,int>> sol;
    for(muchie m : muchii)
    {
        if(gaseste(m.a) != gaseste(m.b))
        {
            cst += m.c;
            uneste(m.a, m.b);
            sol.push_back(make_pair(m.a, m.b));
        }
    }

    fout<<cst<<'\n'<<sol.size()<<'\n';
    for(auto m : sol)
    {
        fout<<m.second<<" "<<m.first<<'\n';
    }

    return 0;
}