#include<fstream>
#include<queue>
#include<vector>
using namespace std;
struct arc{int nod, cost;};
ifstream  in("apm.in");
ofstream out("apm.out");
int n,m,x,y,i,j,nrn,c=0,z;
struct cmp{
    bool operator()( arc a, arc b){
        if(a.cost>b.cost) return 1;
        return 0;
    }
};
priority_queue<arc, vector <arc> , cmp> q;
vector <arc> l[20005];
int t[20005];
bool viz[20005];
vector <int> d(20005,99999999);
int main(){
    in>>n>>m;
    for(i=1;i<=m;++i){ in>>x>>y>>z; l[x].push_back((arc){y,z}); l[y].push_back((arc){x,z});}
    nrn=n;
    q.push((arc){1,0});
    d[0]=d[1]=0; viz[0]=1;
    while(nrn){
        x=0;
        while(viz[x]) { x=q.top().nod; q.pop();}
        viz[x]=1; c+=d[x];
        --nrn;
        for(vector <arc> :: iterator it=l[x].begin(); it!=l[x].end();++it){
            if(d[(*it).nod] > (*it).cost && !viz[(*it).nod]){
                t[(*it).nod]=x;
                d[(*it).nod]=(*it).cost;
                q.push((*it));
            }
        }
    }
    out << c << '\n' << n - 1 << '\n';
    for ( i = 2; i <= n; ++i )
        out << i << ' ' << t[ i ] << '\n';
    return 0;
}