#include<bits/stdc++.h>
#include<algorithm>
#define Dim 10000
using namespace std;
typedef struct Muchie {int e1,e2,cost;};
Muchie G[Dim];
int A[Dim],c[Dim],n,m,T[Dim];
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;
        T[i]=G[i].cost;
        }
    for(i=1;i<=n;i++)
        c[i]=i;
}
void sortare(int st,int dr)
{
    int 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 ss()
{
    int i,j;
    Muchie x;
    for(i=1;i<m;i++)
        for(j=i+1;j<=m;j++)
        if(G[i].cost>G[j].cost)
    {
        x=G[i];
        G[i]=G[j];
        G[j]=x;
    }
}

void afisare(int M)
{
    int 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()
{
    int i,j,min_c,max_c,M=0,cost,t;
    i=1;
    init();
    //ss();
    sortare(1,m);
    //sort(G+1,G+m);
    //qs(1,m);
    //for(t=1;t<=m;t++) cout<<G[t].cost<<' ';
    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;
}