#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define mx 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector< pair< int, pair<int, int> > > vect;
vector<pair<int, int> > vectsol;
int n,m,dad[mx];
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)));
    }
}
int grupa(int nod)
{
    if(dad[nod]==nod) return nod;
    else dad[nod]=grupa(dad[nod]);
    return dad[nod];
}
void unite(int x,int y)
{
    dad[grupa(x)]=grupa(y);
}
int main()
{
    int i,sum=0;
    citire();
    sort(vect.begin(),vect.end());
     for(i=1;i<=n;i++)
        dad[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'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<vectsol[i].second<<" "<<vectsol[i].first<<'\n';
    return 0;
}