///Paduri de multimi disjuncte
#include <bits/stdc++.h>
#define K 200002
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int t[500002],sol[100002];
struct muchie
{
    int x,y,d;
}mc[500002];
bool comp(muchie a,muchie b){return a.d<b.d;}
int tata (int x)
{
    if(t[x]==0)
        return x;
    return tata(t[x]);
}
void compresie(int tt,int fiu)
{
    if(fiu==tt)return ;
    t[fiu]=tt;
    compresie(tt,t[fiu]);
}
int main()
{
    int i,n,m,x,y,tx,ty,ct=0,sum=0;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>mc[i].x>>mc[i].y>>mc[i].d;
    sort(mc+1,mc+m+1,comp);
    for(i=1;i<=m;i++)
    {
        x=mc[i].x;y=mc[i].y;
        tx=tata(x);ty=tata(y);
        if(tx!=ty)
        {
            sol[++ct]=i;sum+=mc[i].d;
            t[ty]=tx;
            compresie(tx,y);
        }
    }
    g<<sum<<"\n"<<n-1<<"\n";
    for(i=1;i<=ct;i++)
        g<<mc[sol[i]].y<<" "<<mc[sol[i]].x<<"\n";
}