#include <stdio.h>

using namespace std;
FILE *f,*g;
int N,M;
struct Edges
{
    int one,two,cost;
};
Edges v[400010];
int BestCost,Number;
struct Answer
{
    int n1,n2;
};
Answer edge[400010];
int Father[200010],Rank[200010];
void BubbleSort()
{
    int i,t=M,aux;
    bool sortat;
    do
    {
        sortat=true;
        for(i=1;i<t;++i)
            if(v[i].cost>v[i+1].cost)
            {
                sortat=false;
                aux=v[i].cost,v[i].cost=v[i+1].cost,v[i+1].cost=aux;
                aux=v[i].one,v[i].one=v[i+1].one,v[i+1].one=aux;
                aux=v[i].two,v[i].two=v[i+1].two,v[i+1].two=aux;
            }
        t--;
    }while(!sortat);
}
void UpdateFather()
{
    int i;;
    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()
{
    BubbleSort();
    UpdateFather();
    int i,A,B;
    for(i=1;i<=M;++i)
    {
        A=FindFather(v[i].one);B=FindFather(v[i].two);
        if(A!=B)
        {
            ++Number;
            Unific(A,B);
            BestCost+=v[i].cost;
            edge[Number].n1=v[i].one,edge[Number].n2=v[i].two;
        }
    }
}
void Displaying()
{
    int i;
    fprintf(g,"%d\n%d\n",BestCost,Number);
    for(i=1;i<=Number;++i)
        fprintf(g,"%d %d\n",edge[i].n2,edge[i].n1);
}
void Read()
{
    fscanf(f,"%d %d",&N,&M);
    int i;
    for(i=1;i<=M;++i)
        fscanf(f,"%d %d %d",&v[i].one,&v[i].two,&v[i].cost);
}
int main()
{
    f=fopen("apm.in","r");g=fopen("apm.out","w");
    Read();APM();Displaying();
    fclose(f);fclose(g);
    return 0;
}