#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
priority_queue<pair<int,pair<int,int> > >muchii;
vector <pair<int,int> > graf_final;
int tata[200001];
int grad[200001];

int find_tata(int nod)
{
    if (tata[nod]==nod) return nod;
    tata[nod]=find_tata(tata[nod]);
    return tata[nod];
}
int main()
{
    int N,M,i,x,y,c;
    fin>>N>>M;
    for(i=1;i<=N;i++)
    {
        grad[i]=1;
        tata[i]=i;
    }
    for(i=0;i<M;i++)
    {
        fin>>x>>y>>c;
        muchii.push(make_pair((-1)*c,make_pair(x,y)));
    }
    int cost=0;
    while(!muchii.empty())
    {
        pair<int,int>muchie;
        pair<int,pair<int,int> > p=muchii.top();
        muchii.pop();
        muchie=p.second;

        int t_first,t_second;
        t_first=find_tata(muchie.first);
        t_second=find_tata(muchie.second);

        if(t_first!=t_second)
        {
            if(grad[t_first]<grad[t_second])
            {
                tata[t_first]=t_second;
                grad[t_second]+=grad[t_first];
                graf_final.push_back(make_pair(muchie.first,muchie.second));
                cost+=(-1)*p.first;

            }
            else
            {
                tata[t_second]=t_first;
                grad[t_first]+=grad[t_second];
                graf_final.push_back(make_pair(muchie.first,muchie.second));
                cost+=(-1)*p.first;
            }

        }
    }

    fout<<cost<<endl;
    fout<<graf_final.size()<<endl;
    for(i=0;i<graf_final.size();i++)
     fout<<graf_final[i].first<<" "<<graf_final[i].second<<endl;
    return 0;
}