#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 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;
    viz[1]=1;
    for(i=1;i<=n-1;i++){
        it=a.begin();
        nod=(*it).second;
        a.erase(it);
        viz[nod]=1;
        for(j=0;j<nre[nod];j++){
            if(c[v[nod][j].first]>v[nod][j].second){
                if(t[nod]!=v[nod][j].first){
                    c[v[nod][j].first]=v[nod][j].second;
                    t[v[nod][j].first]=nod;
                }
                if(!viz[v[nod][j].first]){
                    a.insert(make_pair(c[v[nod][j].first],v[nod][j].first));

                }
            }
        }
    }
    for(i=1;i<=n;i++){
        cost+=c[i];
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        g<<i<<' '<<t[i]<<'\n';
    return 0;
}