#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

#define NMAX 300005
vector<pair<int, int> > graf;
priority_queue<pair<int, pair<int, int> > >coada;

int n, m, tata[NMAX], rang[NMAX], ct;
void citire()
{
    f>>n>>m;
    for(int i = 0; i < m; i ++)
    {

        int a,b,c;
        f>>a>>b>>c;
        coada.push({-c,{a,b}});
        coada.push({-c,{b,a}});
    }

}


int father(int x)
{
    if(tata[x] == x)
        return x;
    tata[x] = father(tata[x]);
    return tata[x];
}
void unite(int x, int y)
{

    if(rang[x] < rang[y])
    {
        tata[x] = y;
        rang[y] += rang[x];
    }
    else
    {
        tata[y] = x;
        rang[x] += rang[y];
    }
}
void KRUSKAL()
{
    for(int i = 1; i <= n; i ++)
    {
        tata[i] = i;
        rang[i] = 1;
    }
    while(!coada.empty())
    {

        pair<int, pair<int, int> > best = coada.top();
        coada.pop();

        int nod1 = best.second.first;
        int nod2 = best.second.second;
        int cost = -best.first;

        if(father(nod1) != father(nod2))
        {
            graf.push_back({nod1,nod2});
            ct += cost;
            unite(father(nod1), father(nod2));
        }

    }


}


void afisare()
{
    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(int i = 0; i < n-1; i ++)
    {
        g<<graf[i].first<<' '<<graf[i].second<<'\n';
    }
}
int main()
{
   citire();
   KRUSKAL();
   afisare();
    return 0;
}