#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int maxn = 400100;
int GR[maxn],X[maxn],Y[maxn],C[maxn],N,M,ANS,IND[maxn],i;
vector<int> VANS;
int grupa(int i)
{
    if (GR[i] == i) return i;
    GR[i] = grupa(GR[i]);
    return GR[i];
}
void reuniune(int i,int j)
{
    GR[grupa(i)] = grupa(j);
}
bool cmpf(int i,int j)
{
    return(C[i] < C[j]);
}
int main()
{
  f>>N>>M;
    for(i = 1;i <= M;++i)
    {
        f>>X[i]>>Y[i]>>C[i];
        IND[i] = i;
    }
    for(i = 1;i <= N; ++i) GR[i] = i;
    for(i = 1;i <= N; ++i) GR[i] = i;
    sort(IND + 1,IND + M + 1,cmpf);
    for(i = 1;i <= M; ++i)
    {
        if (grupa(X[IND[i]]) != grupa(Y[IND[i]])){
            ANS += C[IND[i]];reuniune(X[IND[i]],Y[IND[i]]);
            VANS.pb(IND[i]);
        }
    }
    g<<ANS<<'\n';
    g<<N-1<<'\n';
    for(i = 0;i < N - 1; ++i)
        g<<X[VANS[i]]<<" "<<Y[VANS[i]]<<'\n';
    return 0;
}