#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int p[200001],n,m,i,q,x,y,c,rasp;

///vector<pair<int,int> > v[200001];
vector<pair<int,pair<int,int> > > v;

int fp(int x)
{
    if (x!=p[x])
        p[x]=fp(p[x]);
    return p[x];
}

void unite(int x,int y)
{

    p[x]=y;
}

int main()
{
    f>>n>>m;
    int mm=m;
    while(mm--)
    {
        f>>x>>y>>c;
        v.push_back(make_pair(c,make_pair(x,y)));
    }

    sort(v.begin(),v.end());

    for (i=1;i<=n;++i)
        p[i]=i;

    for (i=0;i<m;++i)
    {
        x = fp(v[i].second.first);
        y = fp(v[i].second.second);
        if (x != y)
            unite(x,y),rasp+=v[i].first,v.push_back(make_pair(c,make_pair(x,y)));
    }

    g<<rasp<<'\n'<<v.size()-m<<'\n';
    for(i=m;i<v.size();++i)
        g<<v[i].second.first<<" "<<v[i].second.second<<'\n';

    return 0;
}