#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int TT[200001];
struct muchie
{
    int a,b,val;
} edges[400001],aux[400001],sol[400001];
int n,m,cost,noduri;
void Interclasare(int low,int mid,int high)
{
    int i=low,j=mid+1,k=low-1;
    while(i<=mid && j<=high)
    {
        if(edges[i].val<edges[j].val)
            aux[++k]=edges[i++];
        else aux[++k]=edges[j++];
    }

    while(i<=mid)
        aux[++k]=edges[i++];

    while(j<=high)
        aux[++k]=edges[j++];

    for(int i=low; i<=k; i++)
        edges[i]=aux[i];
}
void MergeSort(int low,int high)
{
    if(low<high)
    {
        int mid=low+(high-low)/2;
        MergeSort(low,mid);
        MergeSort(mid+1,high);

        Interclasare(low,mid,high);
    }
}
int root(int x)
{
    int parinte,rad=x;
    while(TT[rad]!=0)
        rad=TT[rad];

    while(x!=rad)
    {
        parinte=TT[x];
        TT[x]=rad;
        x=parinte;
    }
    return rad;
}
void Unite(int I,int J)
{
    I=root(I);
    J=root(J);
    TT[I]=J;
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>edges[i].a>>edges[i].b>>edges[i].val;

    MergeSort(1,m);

    for(int i=1; i<=m; i++)
    {
        int Tata_a=root(edges[i].a);
        int Tata_b=root(edges[i].b);

        if(Tata_a!=Tata_b)
        {
            Unite(Tata_a,Tata_b);
            cost+=edges[i].val;
            sol[noduri++]=edges[i];
        }
    }

    g<<cost<<'\n'<<noduri<<'\n';
    for(int i=0; i<noduri; i++)
        g<<sol[i].a<<" "<<sol[i].b<<'\n';
    return 0;
}