#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct Bla
{
    int node1,node2,price;
};
Bla v[400010];
struct Bla2
{
    int fn,sn;
};
Bla2 solution[400010];
int Father[200010],Rank[200010];
int N,M,Answer,K;
bool Critery(Bla A, Bla B)
{
    if(A.price!=B.price)return(A.price<B.price);
}
void Read()
{
    int i,j;
    fscanf(f,"%d %d",&N,&M);
    for(i=1;i<=M;++i)
        fscanf(f,"%d %d %d",&v[i].node1,&v[i].node2,&v[i].price);
    sort(v+1,v+1+M,Critery);
    for(i=1;i<=N;++i)Father[i]=i;
}
int FindFather(int Node)
{
    if(Node!=Father[Node])
        Father[Node]=FindFather(Father[Node]);
    return Father[Node];
}
void Unific(int A,int B)
{
    if(Rank[A]>Rank[B])
        Father[B]=A;
   else
        Father[A]=B;
    if(Rank[A]==Rank[B])++Rank[B];
}
void APM()
{
    int dad1,dad2,X,Y,i;
    for(i=1;i<=M;++i)
    {
        X=v[i].node1,Y=v[i].node2;
        dad1=FindFather(X),dad2=FindFather(Y);
        if(dad1==dad2)continue;
        Unific(dad1,dad2);
        Answer+=v[i].price,++K;
        solution[K].fn=X,solution[K].sn=Y;
    }
}
void Displaying()
{
    fprintf(g,"%d\n%d\n",Answer,K);
    int i;
    for(i=1;i<=K;++i)
        fprintf(g,"%d %d\n",solution[i].fn,solution[i].sn);
}
int main()
{
    f=fopen("apm.in","r");g=fopen("apm.out","w");
    Read();APM();Displaying();
    fclose(f);fclose(g);
    return 0;
}