#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*g;
int N,M;
int Rank[200010],Father[200010];
struct Edges
{
    int A,B,price;
};
Edges v[400010];
struct Tree
{
    int a,b;
};
Tree tree[400010];
void FatherUpdate()
{
    int i;
    for(i=1;i<=N;i++)Father[i]=i;
}
void Read()
{
    fscanf(f,"%d %d",&N,&M);
    int i;
    for(i=1;i<=M;i++)
        fscanf(f,"%d%d%d",&v[i].A,&v[i].B,&v[i].price);
    FatherUpdate();
}
bool Critery(Edges X,Edges Y)
{
    return (X.price<Y.price);
}
int FindFather(int NOD)///caut radacina arborelui si actualizez tatal fiecarui nod
{
    if(NOD!=Father[NOD])
        Father[NOD]=FindFather(Father[NOD]);
    return Father[NOD];
}
void Joining(int X,int Y)///unesc cele doua noduri in functie de marimea arborelui din care fac parte fiecare
{
    if(Rank[X]<Rank[Y])Father[X]=Y;
    else Father[Y]=X;
    if(Rank[X]==Rank[Y])///in caz ca sunt egale, cresc rangul unuia dintre ele
        ++Rank[X];
}
int NumberEdgesTree,PriceTree;
void Solve()
{
    sort(v+1,v+1+M,Critery);
    int X,Y,AA,BB,i=0;
    while(M)
    {
        M--;
        X=v[++i].A;Y=v[i].B;
        AA=FindFather(X);
        BB=FindFather(Y);
        if(AA==BB)continue;///daca fac parte din acelas arbore, nu le mai unesc
        Joining(AA,BB);
        PriceTree+=v[i].price;
        ++NumberEdgesTree;
        tree[NumberEdgesTree].a=X,tree[NumberEdgesTree].b=Y;
    }
}
void Displaying()
{
    fprintf(g,"%d\n%d\n",PriceTree,NumberEdgesTree);
    while(NumberEdgesTree)
    {
        fprintf(g,"%d %d\n",tree[NumberEdgesTree].a,tree[NumberEdgesTree].b);
        --NumberEdgesTree;
    }
}
int main()
{
    f=fopen("apm.in","r");g=fopen("apm.out","w");
    Read();Solve();Displaying();
    fclose(f),fclose(g);
    return 0;
}