#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 400002

using namespace std;

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

int N,M,APM,T[NMAX>>1];
struct muchie{
    int x,y,c;
}V[NMAX];

vector<pair<int,int> >Sol;


class cmp
{
    public:
    inline bool operator()(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 main()
{
    int i,m1,m2;
    in>>N>>M;
    for(i=0;i<M;i++)
        in>>V[i].x>>V[i].y>>V[i].c;
    //sortez muchiile crescator dupa cost

    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));
        }
    }
    out<<APM<<'\n'<<N-1<<'\n';
    for(i=0;i<N-1;i++)
        out<<Sol[i].first<<' '<<Sol[i].second<<'\n';
    return 0;
}