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

using namespace std;

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

const int NMAX  = 2e5 + 5;

int n, m;
int ind[NMAX], cost[NMAX], x[NMAX], y[NMAX];
int TT[NMAX], RG[NMAX];

bool cmp(const int &a, const int &b)
{
    return cost[a] < cost[b];
}

int find(int a)
{
    if(TT[a] != a)
        TT[a] = find(TT[a]);
    return TT[a];
}
void unite(int parent1, int parent2)
{

    if(parent1 == parent2)
        return;

    if(RG[parent1] > RG[parent2])
        TT[parent2] = parent1;
    else
        TT[parent1] = parent2;
    
    if(RG[parent1] == RG[parent2])
        RG[parent2]++;
    
}

void ReadInput()
{
    fin >> n >> m;
    for(int i = 1; i<= m; ++i)
    {
        fin >> x[i] >> y[i] >> cost[i];
        ind[i] = i;
    }

    for(int i = 1; i<= n; ++i)
    {
        TT[i] = i;
        RG[i] = 0;
    }

    sort(ind+ 1, ind + m + 1, cmp);

    vector<pair<int,int> > v;
    int total = 0;
    for(int i = 1; i<=m ; ++i)
    {
        int a = x[ind[i]], b = y[ind[i]];
        int parent1 = find(a), parent2 = find(b);
        if(parent1 != parent2)
        {
            unite(parent1,parent2);
            v.push_back({b,a});
            total+= cost[ind[i]];
        }
    }
    fout << total << '\n' << v.size() << '\n';
    for(int i = 0; i < v.size(); ++i)
    {
        fout << v[i].first << " " << v[i].second << '\n';
    }
}

int main()
{
    ReadInput();
    return 0;
}