#include <iostream>
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod
{
    int info;
    nod *leg;
};
nod *lprim[400010],*lultim[400010];
#define Nmax 400001
int i,n,m,X[Nmax],Y[Nmax],C[Nmax],IND[Nmax],cst=0;
void reuniune(int i,int j)
{
    lultim[i]->leg=lprim[j];
    lultim[i]=lultim[j];
    lprim[j]=lprim[i];
}
bool gasit(int i,int j)
{
    nod *p,*q;
    p=lprim[i];
    q=lprim[j];
    while(p!=NULL && p->leg!=NULL) p=p->leg;
    while(q!=NULL && q->leg!=NULL) q=q->leg;
    if(p->info==q->info) return 1;
    else return 0;
}
bool comp(int i,int j)
{
    return C[i]<C[j];
}
vector<int>v;
int main()
{
    nod *p;
    for(i=0;i<=10001;i++)
    {
        p=new nod;
        p->leg=NULL;
        p->info=i;
        lprim[i]=lultim[i]=p;
    }
    f>>n>>m;
    for(i=1;i<=m;i++) {f>>X[i]>>Y[i]>>C[i];IND[i]=i;}
    sort(IND+1,IND+m+1,comp);
    for(i=1;i<=m;i++)
        if(!gasit(X[IND[i]],Y[IND[i]]))
    {
        cst+=C[IND[i]];
        reuniune(X[IND[i]],Y[IND[i]]);
        v.push_back(IND[i]);
    }
    g<<cst<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++) g<<X[v[i]]<<' '<<Y[v[i]]<<'\n';
}