#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct vec{int x,y,c;}A[400001];
struct save{int x; save *urm;};
int n,m,x,y,c,S,i,k,T[200001];
save *X;
bool li(vec x, vec y) {return x.c < y.c;}
int Tata(int x)
{
    if(T[x] != x) T[x]=Tata(T[x]);
    return T[x];
}
void Adauga(int x) {save *aux=new save; aux->x=x; aux->urm=X; X=aux;}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>A[i].x>>A[i].y>>A[i].c;
    sort(A+1,A+m+1,li);
    for(i=1;i<=n;i++) T[i]=i;
    i=1;
    while(k<n-1)
    {
        x = Tata(A[i].x), y = Tata(A[i].y);
        if(x == y) i++;
        else
        {
            T[x] = y;
            S += A[i].c;
            Adauga(i);
            k++;
        }
    }
    cout<<S<<'\n'<<n-1<<'\n';
    while(X) cout<<A[X->x].x<<' '<<A[X->x].y<<'\n',X=X->urm;
}