#include <fstream>
#include<vector>
#include<queue>
#define INF 1001
using namespace std;

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

struct nodul{
    int vf, c;
};

vector<nodul> a[200001];
int n,m,x,poz[200001],h[200001],nh,d[200001],predec[200001],ct;
bool t[200001];

void schimba (int x, int y){
    int u=h[x];
    h[x]=h[y];
    h[y]=u;
    poz[h[x]]=x;
    poz[h[y]]=y;
}

void coboara(int i){
     int fs = 2*i, fd = 2*i + 1, bun = i;
    if (fs <= nh && d[h[fs]] < d[h[bun]])
        bun = fs;
    if (fd <= nh && d[h[fd]] < d[h[bun]])
        bun = fd;
    if (bun != i) {
        schimba(i, bun);
        coboara(bun);
    }
}
void sterg(int i){
    schimba(i,nh);
    nh--;
    coboara(1);
}


void urc(int i ){
    while(i>=2 && d[h[i]]<d[h[i/2]]){
        schimba(i,i/2);
        i/=2;
    }
}

void adaug(int x)
{
    h[++nh] = x;
    poz[x] = nh;
    urc(nh);
}

void dijkstra(int xnod){
    int y,cost;
    for (int i = 1; i <= n; i++)
            d[i] = INF;
    d[xnod] = 0;
    poz[1]=1;
    adaug(xnod);
    while(nh != 0){
        xnod=h[1];
        t[x]=true;
        sterg(1);
        ct += d[xnod];
        for(unsigned i=0;i<a[xnod].size(); i++){
            y= a[xnod][i].vf;
            cost = a[xnod][i].c;
            if(!t[y] && cost < d[y]){
                d[y] = cost;
                predec[y]=xnod;
                if (poz[y] == 0){
                    //predec[y]=xnod;
                    adaug(y);
                }
                else
                    urc(poz[y]);
            }
        }
        //for (int i = 1; i <= nh; i++)
        //    out<< "(" << h[i] << "," << d[h[i]] << ") " ;
        //out<< "\n";
    }
}


int main()
{
    int i,na,nb,c;
    in>>n>>m;

    for(i=1;i<=m;i++){
        in>>na>>nb>>c;
        a[na].push_back((nodul){nb,c});
        a[nb].push_back((nodul){na,c});
    }
    dijkstra(1);
    out<<ct<<"\n"<<n-1<<"\n";
    for(i=2;i<=n;i++)
        out<<i<<" "<<predec[i]<<"\n";
    return 0;
}