#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 400002
using namespace std;
ifstream f("apm.in"); ofstream g("apm.out");
int N,M,APM,T[NMAX>>1];
struct muchie {int x,y,c;} V[NMAX];
vector<pair<int,int> >Sol;
inline bool cmp(const muchie&a,const muchie&b) {return a.c<b.c;}
/*
int multime(int x)
{   if(!T[x])return x;
    T[x] = multime(T[x]);
    return T[x];
}
*/
int multime(int x)
{   while(T[x]) x=T[x];
    return x;
}
int main()
{   int i,m1,m2;
    f>>N>>M;
    for(i=0;i<M;i++) f>>V[i].x>>V[i].y>>V[i].c;
    sort(V,V+M,cmp);
    for(i=0;i<M;i++)
    {   m1 = multime(V[i].x); m2 = multime(V[i].y);
        if(m1!=m2)
        {   APM+=V[i].c,T[m2]=m1;
            Sol.push_back(make_pair(V[i].x,V[i].y));
        }
    }
    g<<APM<<'\n'<<N-1<<'\n';
    for(i=0;i<N-1;i++) g<<Sol[i].first<<' '<<Sol[i].second<<'\n';
    return 0;
}