#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair < int,int > P[400005];
struct muchie{
    int x,y,cost;
}muchii[400005];

int n,m, tata[200005], rang[200005],total,k;

bool compara(muchie a, muchie b)
{
    return a.cost < b.cost;
}


void citire()
{
    fin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
    }
    for(int i=1;i<=n;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    sort(muchii+1, muchii+m+1, compara );
}


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

void unire(int nod1, int nod2)
{
    if(rang[nod1]>rang[nod2])
    {
        tata[nod2]=nod1;
    }
    if(rang[nod1]<rang[nod2])
    {
        tata[nod1]=nod2;
    }
    if(rang[nod1]==rang[nod2])
    {
        tata[nod1]=nod2;
        rang[nod2]++;
    }
}

void rezolva()
{
    k=0;
    for(int i=1;i<=m;i++)
    {
        int tata1=gaseste( muchii[i].x );
        int tata2=gaseste(muchii[i].y);
        if( tata1 != tata2)
        {
            unire( gaseste(muchii[i].x ) ,  gaseste(muchii[i].y) );
            k++;
            P[k].first=muchii[i].x;
            P[k].second=muchii[i].y;
            total=total+muchii[i].cost;
        }
    }
}


int main()
{
citire();
rezolva();
fout<<total<<endl;
fout<<k<<endl;
for(int i=1;i<=k;i++)
{
    fout<<P[i].first<<" "<<P[i].second<<endl;
}


return 0;
}