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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

const int MMax = 400005, NMax = 200005;

vector <pair <int, int> > Sol;

int n, m, t[NMax], sum;

struct Muchie
{
    int x, y, cost;
} a[NMax];

bool Crit(Muchie a1, Muchie a2)
{
    return a1.cost < a2.cost;
}

void Read()
{
    f>>n>>m;
    for(int i = 1; i <= m; i++) f>>a[i].x>>a[i].y>>a[i].cost;
    sort(a+1, a+m+1, Crit);
    for(int i = 1; i <= n ; i++) t[i] = i;
}

int Tata(int d)
{
    while(d != t[d]) d = t[d];
    return d;
}

void Unite(int d, int c)
{
    t[d] = c;
}

void Solve()
{
    for(int i = 1; i <= m; i++)
    {
        if(Tata(a[i].x) != Tata(a[i].y))
        {
            sum += a[i].cost;
            Unite(Tata(a[i].x), Tata(a[i].y));
            Sol.push_back(make_pair(a[i].x,a[i].y));
        }
    }
}

void Print()
{
    g<<sum<<'\n';
    g<<Sol.size()<<'\n';
    for(int i = 0; i < (int)Sol.size(); i++) g<<Sol[i].first<<' '<<Sol[i].second<<'\n';
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}