#include <fstream>
#include <set>
#include <vector>
#include <limits.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
multiset <pair<int,int> > a;
multiset <pair<int,int> > ::iterator it;
vector <pair<int,int> >v[200001];
int n,k,x,y,z,i,j,nod,nre[200001],c[200001],t[200001],viz[200001],cost;
/*int tata(int nod){
    while(t[nod]!=0)
        nod=t[nod];
    return nod;
}*/
int main()
{
    f>>n>>k;
    for(i=1;i<=k;i++){
        f>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    for(i=1;i<=n;i++){
        nre[i]=v[i].size();
        c[i]=INT_MAX;
    }
    a.insert(make_pair(0,1));
    c[1]=0;

    for(i=1;i<=n-1;i++){
        it=a.begin();
        nod=(*it).second;
        a.erase(it);
        viz[nod]=1;cost+=c[nod];
        for(j=0;j<nre[nod];j++){
            int nodact=v[nod][j].first;
            int costact=v[nod][j].second;
            if(c[nodact]>costact){
                if(!viz[nodact]){
                    it=a.find(make_pair(c[nodact],nodact));
                    if(it!=a.end())
                        a.erase(it);
                    c[nodact]=costact;
                    t[nodact]=nod;

                    a.insert(make_pair(costact,nodact));
                }
            }
        }
    }
         it=a.begin();
        nod=(*it).second;
        a.erase(it);
        viz[nod]=1;cost+=c[nod];
    g<<cost<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        g<<i<<' '<<t[i]<<'\n';
    return 0;
}