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

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

const int Nmax = 200005;

int n, m, s, TT[Nmax], R[Nmax];
struct Muchie
{
    int x, y, cost;
}G[Nmax];
vector <pair <int, int> > sol;

bool Crit(Muchie a, Muchie b)
{
    return a.cost<b.cost;
}

void Unite(int x, int y)
{
    if(R[x] == R[y])
    {
        TT[x] = y;
        R[y]++;
    }
    else if(R[y] > R[x]) TT[x] = y;
    else TT[y] = x;
}

int tata(int nod)
{
    while(nod != TT[nod]) nod = TT[nod];
    return nod;
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= n; i++) TT[i] = i;
    for(int i = 1; i <= m; i++)
        f>>G[i].x>>G[i].y>>G[i].cost;
    sort(G+1, G+m+1, Crit);
    for(int i = 1; i <= m; i++)
    {
        if(tata(G[i].x) != tata(G[i].y))
        {
            Unite(tata(G[i].x), tata(G[i].y));
            sol.push_back(make_pair(G[i].x,G[i].y));
            s += G[i].cost;
        }
    }
    g<<s<<'\n'<<sol.size()<<'\n';
    for(int i = 0; i < (int)sol.size(); i++) g<<sol[i].first<<' '<<sol[i].second<<'\n';
    return 0;
}