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

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

struct Muchie{
    int s, f, c;
};

vector<Muchie> l;
vector<int> sol;
int n, m, R[1000000], costMin;

bool ordC(Muchie a, Muchie b)
{
    return a.c < b.c;
}

int reprez(int x)
{
    if(R[x] == x)
        return x;
    R[x] = reprez(R[x]);
    return R[x];
}

void reuniune(int x, int y)
{
    R[reprez(x)] = reprez(y);
}

int main()
{
    int a, b, c;
    in>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        in>>a>>b>>c;
        l.push_back({a, b, c});
    }
    sort(l.begin(), l.end(), ordC);
    for(int i = 1; i <= n; i++)
        R[i] = i;
    for(int i = 0; i < l.size(); i++)
        if(reprez(l[i].s) != reprez(l[i].f))
        {
            reuniune(l[i].s, l[i].f);
            costMin += l[i].c;
            sol.push_back(i);
        }
    out<<costMin<<"\n"<<sol.size()<<"\n";
    for(auto it: sol)
        out<<l[it].s<<" "<<l[it].f<<"\n";
    return 0;
}