#include <iostream>
#include <fstream>
#include <algorithm>
#define MAX 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair <int ,int> p[MAX];
int pas;
int n,m;
int total;
int tati[MAX];
int rang[MAX];
struct muchie{
   int x;
   int y;
   int cost;
}M[MAX];
bool comparator(muchie a,muchie b)
{
    return a.cost<b.cost;
}
void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>M[i].x;
        fin>>M[i].y;
        fin>>M[i].cost;
    }
    sort(M+1,M+m+1,comparator);
    for(int i=1;i<=n;i++)
    {
        tati[i]=i;
        rang[i]=1;
    }
}
int cautare(int nod)
{
    while(tati[nod]!=nod)
    {
        nod=tati[nod];
    }
    return nod;
}
void unire(int x,int y)
{
    if(rang[x]<rang[y])
        tati[x]=y;
    if(rang[x]>rang[y])
        tati[y]=x;
    if(rang[x]==rang[y])
    {
        tati[x]=y;
        rang[y]++;
    }
}
void kruskal()
{
    for(int i=1;i<=m;i++)
    {
        int tatax=cautare(M[i].x);
        int tatay=cautare(M[i].y);
        if(tatax!=tatay)
        {
            unire(tatax,tatay);
            p[++pas]=make_pair(M[i].x,M[i].y);
            total=total+M[i].cost;
        }
    }
}
void afisare()
{
    fout<<total<<'\n';
    fout<<pas<<'\n';
    for(int i=1;i<=pas;i++)
    {
        fout<<p[i].first<<" "<<p[i].second<<'\n';
    }
}
int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}