#include <fstream>
#include <set>
#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];
struct much{int c;int x;int y; bool friend operator <(much m1,much m2){return((m1.c<m2.c)||(m1.c==m2.c && m1.x<m2.x)||(m1.c==m2.c && m1.x==m2.x && m1.y<m2.y));}};
vector <much> hart;
vector < pair<int, int> > sol;
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;
}
void citire()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X>>Y>>C;
        much m={C,X,Y};
        hart.push_back(m);
    }
}
void Kruskal()
{
    create_groups();
    sort(hart.begin(), hart.end());
    while(!hart.empty() || nrgrup!=1)
    {
        int nod1=(*(hart.begin())).x;
        int nod2=(*(hart.begin())).y;
        int cost=(*(hart.begin())).c;
        if(Find(nod1)!=Find(nod2))
        {
            Union(nod1,nod2);
            sol.push_back( make_pair(nod2, nod1));
            cost_total=cost_total+cost;
        }
        hart.erase(hart.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;
}