#include <fstream>
#include <cstring>
#include <algorithm>

#define X1 200001
#define X2 400001

using namespace std;

ifstream in;
ofstream out;

pair <int,pair<int,int> > v[X2];
int T[X1],sol[X1];

inline void f(int nod)
{
    if(T[nod]!=nod) f(T[nod]);
    T[nod]=T[T[nod]];
}

int main()
{
    int M,N,x,y,c,sum=0;

    in.open("apm.in");
    in>>N>>M;
    for(int i=1;i<=M;++i)
        in>>v[i].second.first>>v[i].second.second>>v[i].first;
    in.close();

    sort(v+1,v+M+1);

    memset(T,0,sizeof(T));
    memset(sol,0,sizeof(sol));

    for(int i=1;i<=N;++i) T[i]=i;

    for(int i=1;i<=M;++i)
    {
        x=v[i].second.first;
        y=v[i].second.second;
        c=v[i].first;

        f(x);
        f(y);

        if(T[x]!=T[y])
        {
            T[T[x]]=T[y];
            sum+=c;
            sol[++sol[0]]=i;
        }
    }

    out.open("apm.out");
    out<<sum<<'\n'<<N-1<<'\n';
    for(int i=1;i<=sol[0];i++)
        out<<v[sol[i]].second.first<<' '<<v[sol[i]].second.second<<'\n';
    out.close();

    return 0;
}