#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x,y,cost;};
muchie M[400010],sol[400010];
int n,m,k,ct,T[200010];
int rad(int x)
{
    while(T[x]!=0)x=T[x];
    return x;
}
void compresie(int x)
{
    int r,y;
    r=rad(x);
    while(T[x]!=0)
    {
        y=T[x];T[x]=r;x=y;
    }
}
void reuneste(int x,int y){T[x]=y;}
bool cmp(muchie x,muchie y)
{
    return x.cost<y.cost;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>M[i].x>>M[i].y>>M[i].cost;
    }
    sort(M+1,M+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(rad(M[i].x)!=rad(M[i].y))
        {
            k++;
            ct+=M[i].cost;
            reuneste(M[i].x,M[i].y);
            compresie(M[i].y);
            compresie(M[i].x);
            sol[k].x=M[i].x;
            sol[k].y=M[i].y;
        }
        if(k==n-1)break;
    }
    fout<<ct<<'\n'<<k<<'\n';
    for(int i=1;i<=k;i++)
    {
        fout<<sol[i].x<<" "<<sol[i].y<<'\n';
    }
    return 0;
}