#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define y second.second
#define x second.first
#define c first
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int i,j,p[200010],n,m,a,b,now,z,c;
vector< pair<int, pair<int, int> > > v;
queue< pair<int, pair<int, int> > > q;
long long int s;
int parinte(int nod)
{
    if(p[nod]==0)
        return nod;
    return p[nod]=parinte(p[nod]);
    /// eficientizarea : return p[nod] = parinte(p[nod])
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>a>>b>>c,v.push_back(make_pair(c,make_pair(a,b)));
    sort(v.begin(),v.end());

    for(i=0;i<m;i++)
    {
        a=parinte(v[i].x);
        b=parinte(v[i].y);
        if(a != b)
        {
            //fout<<v[i].x<<" "<<v[i].y<<" "<<v[i].c<<'\n';
            p[a]= b;
            s+=v[i].c;
            q.push(v[i]);
        }
    }
    fout<<s<<"\n";
    fout<<q.size()<<'\n';
    while(q.size())
    {
        fout<<q.front().x<<" "<<q.front().y<<"\n";
        q.pop();
    }
    return 0;
}