#include<bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,T[10001],P[10001],i,k,ct;
struct arb{
int x,y,c;
}sol[100001],u[100001];
bool cmp(arb a,arb b)
{
    return a.c<b.c;
}
int root(int x)
{
    while(x!=T[x])
        x=T[x];
        return x;
}
void unifica(int x,int y)
{
    if(P[x]<P[y])
        T[x]=y;
    if(P[x]>P[y])
        T[y]=x;
    if(P[x]==P[y])
    {
        T[y]=x;
        P[x]++;
    }
}
int main ()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
       {
           f>>u[i].x>>u[i].y>>u[i].c;
           T[i]=i;
       }
    sort(u+1,u+m+1,cmp);
    i=1;
    while(k<n-1)
    {
       int rx=root(u[i].x);
        int ry=root(u[i].y);
        if(rx!=ry)
        {
            k++;
            ct+=u[i].c;
            sol[k]=u[i];
            unifica(rx,ry);
        }
        i++;
    }
    g<<ct<<'\n'<<k<<'\n';
    for(i=1;i<=n;i++)
        g<<sol[i].y<<" "<<sol[i].x<<'\n';
    return 0;
}