#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int nmax=200000, cmax=1000;

struct str{
    int nod,muchie;
};

struct cmp{
    bool operator()(str x, str y){
        return x.muchie>y.muchie;
    }
};

str int_str(int nod,int muchie){
    str sol;
    sol.nod=nod;
    sol.muchie=muchie;
    return sol;
}

priority_queue < str, vector <str>, cmp > h;

vector <str> g[nmax+1];

bool u[nmax+1];

int r[nmax+1], d[nmax+1],vsol[nmax][2], sol, nsol;

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        fin>>x>>y>>z;
        z=z+cmax;
        g[x].push_back(int_str(y,z));
        g[y].push_back(int_str(x,z));
    }
    h.push(int_str(1,0));
    r[1]=0;
    d[1]=0;
    for(int i=2;i<=n;i++){
        d[i]=2*cmax+1;
    }
    while(h.empty()==0){
        int x=h.top().nod;
        h.pop();
        if(u[x]==0){
            vsol[nsol][0]=x;
            vsol[nsol][1]=r[x];
            nsol++;
            sol+=d[x];
            u[x]=1;
            for(int i=0;i<int(g[x].size());i++){
                int xn=g[x][i].nod;
                int yn=g[x][i].muchie;
                if(d[xn]>yn){
                    d[xn]=yn;
                    r[xn]=x;
                    h.push(int_str(xn,d[xn]));
                }
            }
        }
    }
    fout<<sol-(n-1)*cmax<<"\n"<<n-1<<"\n";
    for(int i=1;i<=n-1;i++){
        fout<<vsol[i][0]<<" "<<vsol[i][1]<<"\n";
    }
    return 0;
}