#include <bits/stdc++.h>
#define nmax 200002
#define mmax 400002
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n, m , X[mmax], Y[mmax], C[mmax], GR[nmax], IND[mmax], ans;
 vector<int> VANS;
bool comp(int a, int b)
{
    return C[a] < C[b];
}
int grupa(int x)
{
    if(GR[x] == x) return x;
    GR[x]=grupa(GR[x]);
    return GR[x];
}
void reuniune(int x, int y)
{
    GR[grupa(x)] = grupa(y);
}
int main()
{
    in>>n>>m;
    for(int i=0;i<=m;i++)
    {
        in>>X[i]>>Y[i]>>C[i];
        IND[i]= i;
    }
    for(int i=1;i<=n;i++)
    {
        GR[i] = i;
    }
    sort(IND+1, IND+m+1, comp);
    for(int i=1;i<=m;i++)
    {
        if(grupa(X[IND[i]]) != grupa(Y[IND[i]]))
        {
            reuniune(X[IND[i]], Y[IND[i]]);
            ans+=C[IND[i]];
            VANS.push_back(X[IND[i]]);
            VANS.push_back(Y[IND[i]]);
        }
    }
    out<<ans<<'\n';
    out<<n-1<<'\n';
    for(int i=0;i<VANS.size();i+=2)
    {
        out<<VANS[i]<<" "<<VANS[i+1]<<'\n';
    }

}