#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

///Struct
struct Graf{
    int x,y,cost,viz;
};
///Var declaration
Graf a[400005];
int n,m,t[200005],sol;
///Read
void Citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>a[i].x>>a[i].y>>a[i].cost;
}
///Union and Find
void Union(int x,int y){t[y]=x;};
int Find(int x)
{
    int rad,y;
    rad=x;
    while(t[rad]) rad=t[rad];
    while(x!=rad) y=t[x], t[x]=rad, x=y;
    return rad;
}
///Comp
bool Cmp(const Graf A,const Graf B)
{
    return A.cost<B.cost;
}
///Solve
void Rez()
{
    int x,y;
    sort(a+1,a+m+1,Cmp);
    for(int i=1;i<=m;i++)
    {
        x=Find(a[i].x);
        y=Find(a[i].y);
        if(x!=y)
        {
            a[i].viz=1;
            sol+=a[i].cost;
            Union(x,y);
        }
    }
}
///Solution
void Afis(){fout<<sol<<"\n"<<n-1<<"\n";
    for(int i=1;i<=m;i++) if(a[i].viz) fout<<a[i].x<<" "<<a[i].y<<"\n";}
int main()
{
    Citire();
    Rez();
    Afis();
    return 0;
}