#include <bits/stdc++.h>
using namespace std;
#define maxn 200050
#define maxm 400010
ifstream f("apm.in");
ofstream g("apm.out");
int GR[maxn],X[maxn],Y[maxn],C[maxn];
int N,M,IND[maxn],vans;
vector<int> ANS;
int n,m;
void citire(){
    f>>n>>m;
    for(int i=1;i<=m;i++)
        {
            IND[i]=i;
            GR[i]=i;
            f>>X[i]>>Y[i]>>C[i];
        }
}
bool cmp(int a, int b){
    return C[a]<C[b];
}
int grupa(int i){
    int R,y;
    for(R=i; GR[R] != R; R=GR[R]);
    for(;GR[R] != i;){
        y = GR[i];
		GR[i] = R;
		i = y;
    }

    return R;
}
void reuniune(int i, int j){
    GR[grupa(i)]=grupa(j);
}
void afisare(){
    g<<vans<<"\n"<<ANS.size()<<"\n";
    for(int i=0;i<ANS.size();i++)g<<X[ANS[i]]<<" "<<Y[ANS[i]]<<"\n";
}
void fct(){
    for(int i=1;i<=m;i++)
        if(grupa(X[IND[i]])!=grupa(Y[IND[i]]))
    {
        vans += C[IND[i]];
        reuniune(X[IND[i]],Y[IND[i]]);
        ANS.push_back(IND[i]);
    }
}
int main()
{
    citire();
    sort(IND+1,IND+m+1,cmp);
    fct();
    afisare();
    return 0;
}