#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>

#define X1 200001
#define X2 262145
#define INF 1001

using namespace std;

ifstream in;
ofstream out;

vector <pair<int,int> > v[X1];
int H[X2],use[X1],T[X1],pos[X1],D[X1];

inline void up(int nod)
{
    int aux=H[nod];

    while(nod>1&&D[aux]<=D[H[nod>>1]])
    {
        H[nod]=H[nod>>1];
        pos[H[nod]]=nod;
        nod>>=1;
    }

    H[nod]=aux;
    pos[H[nod]]=nod;
}

inline void down(int nod)
{
    int son=0,ind,L,R;

    L=(nod<<1);
    R=(nod<<1)+1;

    if(L<=H[0]) son++;
    if(R<=H[0]) son++;

    if(son==0) return;
    else
    if(son==1) ind=L;
    else
    if(D[H[L]]<D[H[R]]) ind=L;
    else ind=R;

    if(D[H[ind]]<D[H[nod]])
    {
        son=H[nod];
        H[nod]=H[ind];
        H[ind]=son;
        pos[H[ind]]=ind;
        pos[H[nod]]=nod;
        down(ind);
    }
    else return;
}

inline void prim(int nod)
{
    for(vector <pair<int,int> >::iterator it=v[nod].begin();it!=v[nod].end();++it)
        if(!use[(*it).first])
            if(D[(*it).first]>(*it).second)
            {
                D[(*it).first]=(*it).second;
                T[(*it).first]=nod;
                up(pos[(*it).first]);
            }
}

inline void cut()
{
    pos[H[1]]=0;
    H[1]=H[H[0]];
    pos[H[1]]=1;
    H[H[0]]=0;
    H[0]--;
    down(1);
}

int main()
{
    int M,N,x,y,c,nod,sum=0;

    in.open("apm.in");
    in>>N>>M;
    for(;M;--M)
    {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    in.close();

    memset(T,0,sizeof(T));
    memset(D,0,sizeof(D));
    memset(use,0,sizeof(use));
    memset(H,0,sizeof(H));
    memset(pos,0,sizeof(pos));

    for(int i=1;i<=N;++i)
    {
        D[i]=INF;
        H[i]=i;
        pos[i]=i;
    }
    H[0]=N;
    D[1]=0;

    while(H[0])
    {
        nod=H[1];
        use[nod]=1;
        cut();
        prim(nod);
    }

    for(int i=1;i<=N;++i) sum+=D[i];

    out.open("apm.out");
    out<<sum<<'\n'<<N-1<<'\n';
    for(int i=2;i<=N;++i) out<<i<<' '<<T[i]<<'\n';
    out.close();

    return 0;
}