#include <fstream>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct nod{int val;int cost;};
bool operator<(const nod &lhs, const nod &rhs)
{
    return lhs.cost<rhs.cost;
}
int X,Y,C,N,M,muchie[200005],inainte[200005],poz,s;
bool viz[200005];
priority_queue <nod> v[200005];
void make_muchie()
{
    muchie[1]=0;
    for(int i=2;i<=N;i++)
        muchie[i]=9999;
}
int minim_f()
{
    int minim=9999;
    for(int x=1;x<=N;x++)
        if(viz[x]==0)
            if(minim>muchie[x]){minim=muchie[x]; poz=x;}
        return poz;
}
int main()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X>>Y>>C;
        nod aux_1={Y,C};
        v[X].push(aux_1);
        nod aux_2={X,C};
        v[Y].push(aux_2);
    }
    make_muchie();
    for(int i=1;i<N;i++)
    {
        int n=minim_f();
        while(!v[n].empty())
        {
            if(viz[v[n].top().val]==0)
            {
                if(v[n].top().cost<muchie[v[n].top().val])
                {
                    muchie[v[n].top().val]=v[n].top().cost;
                    inainte[v[n].top().val]=n;
                }
            }
            v[n].pop();
        }
        viz[n]=1;
    }
    for(int i=1;i<=N;i++)
        s+=muchie[i];
        fout<<s<<'\n'<<N-1<<'\n';
    for(int i=2;i<=N;i++)
        fout<<i<<' '<<inainte[i]<<'\n';
    return 0;
}