#include <fstream>
#include <set>
#include <vector>
#define INF 20000000
#include <cstdio>
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()
{
    freopen("apm.in", "r",stdin);
    freopen("apm.out", "w",stdout);
    //f>>n>>k;
    scanf("%d %d",&n,&k);
    for(i=1;i<=k;i++){
        //f>>x>>y>>z;
        scanf("%d %d %d",&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]=INF;
    }
    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(!viz[nodact]&&c[nodact]>costact){
                    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));
            }
        }
    }
    cost+=c[(*a.begin()).second];
    //g<<cost<<'\n'<<n-1<<'\n';
    printf("%d\n%d\n",cost,n-1);
    for(i=2;i<=n;i++)
        printf("%d %d\n",i,t[i]);
        //g<<i<<' '<<t[i]<<'\n';
    return 0;
}