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