//scrie costul minim ,numarul de muchii selectate si muchiile
#include <fstream>
#define NMAX 200005
using namespace std;
ifstream intrare("apm.in");
ofstream iesire("apm.out");
struct muchie{int x;int y;int cost;} G[400005], sol[200005];
int tata[NMAX], h[NMAX];
int minim, maxim, num, n, m, p, nr_minim;
int cost_minim; 
 
void citire();
void krushkall();
int Find(int x2);
void Union(int x, int y);
void HeapCombin(int i, int n);
void creaza_Heap();
muchie extract(int &n);
 
int main()
{
	citire();
    creaza_Heap();
    krushkall();
    return 0;
}
 
void citire()
{
    int i;
    intrare>>n>>m;
    for(i=1;i<=m;i++)
        intrare>>G[i].x>>G[i].y>>G[i].cost;
} 
void krushkall()
{
    int i, nr;
    int C1,C2;
    nr=0;
    muchie minim;
    for(i=1;i<=n-1;i++)
    {
        minim=extract(m);
        C1=Find(minim.x);
        C2=Find(minim.y);
        if(C1!=C2)
        {
            cost_minim+=minim.cost;
            Union(C1,C2);
            sol[i]=minim;
        }
        else
            i--;
    }
    iesire<<cost_minim<<'\n';
    iesire<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
		iesire<<sol[i].x<<' '<<sol[i].y<<'\n';
} 
int Find(int x2)
{
    int rad;
    int aux;
    rad=x2;
    while(tata[rad])
        rad=tata[rad];
    aux=x2;
    while(tata[x2])
    {
        aux=x2;
        x2=tata[x2];
        tata[aux]=rad; 
    }
    return rad;
} 
void Union(int x,int y)
{
    if(h[x]>h[y])
        tata[y]=x;
    else
    {
        tata[x]=y;
        if(h[x]==h[y])
            h[y]++;
    }
} 
void HeapCombin(int i, int n)
{
    int fiu, tata;
    int x;
    muchie aux;
    tata=i;
    fiu=2*i;
    x=G[i].cost;
    aux=G[i];
    while(fiu<=n)
    {
        if(fiu+1<=n)
            if(G[fiu].cost>=G[fiu+1].cost)
                fiu++;
        if(x>G[fiu].cost)
        {
            G[tata]=G[fiu];
            tata=fiu;
            fiu=2*tata;
        } 
        else
            break;
    }
    G[tata]=aux;
} 
muchie extract(int &n)
{
    muchie x=G[1];
    G[1]=G[n];
    n--;
    HeapCombin(1,n);
    return x;
} 
void creaza_Heap()
{
    int i;
    for(i=m/2;i>=1;i--)
        HeapCombin(i, m);
}