#include <fstream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int N,M,X,Y,C,g[200005],cost_total,nrgrup,marime[200005];
typedef pair<int, pair<int, int> > muchie;
vector <muchie> harta;
vector < pair<int, int> > sol;
muchie m;
int Find(int nod)
{
    int radacina=nod;
    ///Find
    while(g[radacina]!=radacina)
    {
        radacina=g[radacina];
    }
    ///Compresie
    while(nod!=radacina)
    {
        int next=g[nod];
        g[nod]=radacina;
        nod=next;
    }
    return radacina;
}
void Union(int nod1,int nod2)
{
    if(marime[nod1]>=marime[nod2])
    {
        g[Find(nod2)]=Find(nod1);
        marime[nod1]=marime[nod1]+marime[nod2];
    }
    else
    {
        g[Find(nod1)]=Find(nod2);
        marime[nod2]=marime[nod2]+marime[nod1];
    }
    nrgrup--;
}
void create_groups()
{
    for(int i=1; i<=N; i++)
    {
        g[i]=i;
        marime[i]=1;
    }
    nrgrup=N;
    sort(harta.begin(), harta.end());
}
void citire()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X>>Y>>C;
        m = make_pair(C, make_pair(X,Y));
        harta.push_back(m);
    }
}
void Kruskal()
{
    create_groups();
    while(!harta.empty() || nrgrup!=1)
    {
        int nod1=(*(harta.begin())).second.first;
        int nod2=(*(harta.begin())).second.second;
        int cost=(*(harta.begin())).first;
        if(Find(nod1)!=Find(nod2))
        {
            Union(nod1,nod2);
            sol.push_back( make_pair(nod2, nod1));
            cost_total=cost_total+cost;
        }
        harta.erase(harta.begin());
    }
}
void afis()
{
    fout<<cost_total<<'\n'<<N-1<<'\n';
    for(vector<pair <int, int> > :: iterator it = sol.begin(); it!=sol.end(); it++)
        fout<<(*it).first<<' '<<(*it).second<<'\n';

}
int main()
{
    citire();
    Kruskal();
    afis();
    return 0;
}