#include <iostream>
#include <fstream>
#include <algorithm>
//#define N 200004
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct muchie
{
    int x, y, c;
}G[N];
 
int r[N], rang[N], sol[N];
 
 
void citire(int m)
{
    int i=1;
    while(i<=m)
    {
        fin>>G[i].x>>G[i].y>>G[i].c;
        i++;
    }
}
 
bool conditie(muchie x, muchie y)
{
    return (x.c<y.c);
}
 
int root(int x)
{
    while(r[x])
        x=r[x];
    return x;
}

int algoritm(int m, int n, int &muchii)
{
    int i, Rx, Ry, cost=0;
    for(i=1; i<=n; i++)
        rang[i]=1;
    for(i=1; i<=m && muchii<=n-1; i++)
    {
        Rx=root(G[i].x);
        Ry=root(G[i].y);
        if(Rx!=Ry)
        {
            cost=cost+G[i].c;
            sol[++muchii]=i;
            
            if(rang[Rx]>rang[Ry])
            {
                rang[Rx]=rang[Ry]+rang[Rx];
                r[Ry]=Rx;
            }
            else
            {
                rang[Ry]=rang[Ry]+rang[Rx];
                r[Rx]=Ry;
            }
        }
    }
    return cost;
}
int main()
{
    int n, m, i, muchii=0;
    fin>>n>>m;
    citire(m);
    sort(G+1, G+1+m, conditie);
    fout<<algoritm(m, n, muchii)<<endl;
    fout<<muchii<<endl;
    for(i=1; i<=muchii; i++)
        fout<<G[i].x<<" "<<G[i].y<<" "<<endl;
    return 0;
}