#include<bits/stdc++.h>
#define Nmax 200000
#define Mmax 400000
#define Dim 20000
using namespace std;
typedef struct Muchie {long e1,e2,cost;};
Muchie G[Mmax];
long A[Mmax],c[Nmax],n,m;
void init()
{   int i;
    ifstream fin("apm.in");
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>G[i].e1>>G[i].e2>>G[i].cost;

    for(i=1;i<=n;i++)
        c[i]=i;
}
void sortare(int st,int dr)
{
    unsigned long long i,j;
    Muchie x,y;
        x=G[(st+dr)/2];
        i=st;
        j=dr;
        do
        { while(i<dr && G[i].cost<x.cost) i++;
        while(j>st && G[j].cost>x.cost) j--;
        if(i<=j)
        {   y=G[i];
            G[i]=G[j];
            G[j]=y;
            i++;
            j--;
        }

        } while(i<=j);
        if(st<=j) sortare(st,j);
        if(i<=dr) sortare(i,dr);

}



void afisare(int M)
{
    long i;
    ofstream fout("apm.out");
    int Cost=0;
    for(i=1;i<=n-1;i++)
    {
        //cout<<A[i].e1<<' '<<A[i].e2<<' '<<A[i].cost<<'\n';
        Cost+=G[A[i]].cost;
    }
    fout<<Cost<<'\n';
    fout<<M<<'\n';
    for(i=1;i<=n-1;i++)
    {
        fout<<G[A[i]].e1<<' '<<G[A[i]].e2<<'\n';

    }
}

int main()
{
    long i,j,min_c,max_c,M=0,cost,t;
    i=1;
    init();
    sortare(1,m);

    while(M<n-1)
    {
        if(c[G[i].e1]!=c[G[i].e2])
        {
            A[++M]=i;
        }
        min_c=min(c[G[i].e1],c[G[i].e2]);
        max_c=max(c[G[i].e1],c[G[i].e2]);
        for(j=1;j<=n;j++)
            if(c[j]==max_c) c[j]=min_c;
        i++;
    }
    afisare(M);
    return 0;
}