#include <fstream>
#include <queue>
#include <set>
#include <utility>
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,poz,s,x,drum[200005],inainte[200005];
bool viz[200005];
priority_queue <nod> v[200005];
multiset < pair <int, int> > muchie;
multiset < pair <int, int> >  :: iterator it;
void make_muchie(int sursa)
{
    muchie.insert(make_pair(0,sursa));
    for(int i=1;i<=N;i++)
    {
        drum[i]=9999;
        if(i!=sursa)
            muchie.insert(make_pair(9999,i));
    }
    drum[sursa]=0;
    viz[sursa]=1;
}
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(1);
    while(!muchie.empty())
    {
        it=muchie.begin();
        int n=(*it).second;
        muchie.erase(muchie.begin());
        while(!v[n].empty())
        {
            if(!viz[v[n].top().val])
            {
                it=muchie.find(make_pair(drum[v[n].top().val],v[n].top().val));
                if(it!=muchie.end())
                {
                    if((*it).first>v[n].top().cost)
                    {
                        muchie.erase(it);
                        muchie.insert(make_pair(v[n].top().cost, v[n].top().val));
                        drum[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+=drum[i];
    fout<<s<<'\n'<<N-1<<'\n';
    for(int i=2;i<=N;i++)
        fout<<i<<' '<<inainte[i]<<'\n';
    return 0;
}