#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX=400005;
int p[NMAX], c[NMAX], x[NMAX], y[NMAX], ind[NMAX];
vector<int> sol;
int find(int i)
{
    if(p[i]==i)
        return i;
    p[i]=find(p[i]);
    return p[i];

}
void unite(int i, int j)
{
    p[find(i)]=find(j);
}
inline bool cmp(int i, int j)
{
    return c[i]<c[j];
}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n, m, i, ans=0;
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x[i]>>y[i]>>c[i];
        ind[i]=i;
    }
    for(i=1; i<=n; i++)
        p[i]=i;
    sort(ind+1, ind+m+1, cmp);
    for(i=1; i<=m; i++)
    {
        if(find(x[ind[i]])!=find(y[ind[i]]))
        {
            ans+=c[ind[i]];
            unite(x[ind[i]], y[ind[i]]);
            sol.push_back(ind[i]);
        }
    }
    out<<ans<<'\n'<<n-1<<'\n';
    for(i=1; i<n; i++)
        out<<x[sol[i-1]]<<' '<<y[sol[i-1]]<<'\n';
    return 0;
}