#include<fstream>
#include<vector>
#include<algorithm>
# define mx 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
bool viz[mx];
int n,m,tata[mx],sum;
vector<pair<int, int> >  vectf, vectsol;
vector<pair<int, pair<int, int> > > vect;
void citire()
{
    int i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        vect.push_back(make_pair(c, make_pair(x,y)));
    }
fin.close();
}
int grupa(int nod)
{
    if(tata[nod]==nod) return nod;
    else tata[nod]=grupa(tata[nod]);
    return tata[nod];
}
void unite(int x,int y)
{
    tata[grupa(x)]=grupa(y);
}
int main()
{
    int i;
    citire();
    sort(vect.begin(), vect.end());
    for(i=1;i<=n;i++)
        tata[i]=i;
    for(i=0;i<m;i++)
    {
        if(grupa(vect[i].second.first)!=grupa(vect[i].second.second))
        {
            unite(vect[i].second.first, vect[i].second.second);
        sum+=vect[i].first;
        vectsol.push_back(make_pair(vect[i].second.first, vect[i].second.second));
        }
    }
    fout<<sum<<'\n';
    fout<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<vectsol[i].second<<" "<<vectsol[i].first<<'\n';
    return  0;

}