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

#define MAX 200001
#define BIN 262145

using namespace std;

vector <pair<int,int> > v[MAX];
vector <pair<int,int> >::iterator it;
int H[BIN],pos[MAX],T[MAX],D[MAX],use[MAX];
int cnt;

inline void HeapUp(int nod)
{
    int ind=H[nod];

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

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

inline void HeapDown(int nod)
{
    int ind,L,R,i;

    ind=H[nod];

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

        if(cnt<L)
        {
            H[nod]=ind;
            pos[ind]=nod;
            return;
        }
        else
        if(cnt<R) i=L;
        else
        if(D[H[L]]>D[H[R]]) i=R;
        else i=L;

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

inline void Cut()
{
    pos[H[1]]=0;
    H[1]=H[cnt];
    H[cnt]=0;
    pos[H[1]]=1;
    cnt--;
    HeapDown(1);
}

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

    ifstream in;
    ofstream out;

    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(D,-1,sizeof(D));
    memset(T,0,sizeof(T));
    memset(pos,0,sizeof(pos));
    memset(use,0,sizeof(use));

    cnt=1;
    H[1]=1;
    pos[1]=1;

    while(cnt)
    {
        nod=H[1];
        use[nod]=1;
        if(cnt>1) Cut();
        else
        {
            H[1]=0;
            pos[1]=0;
            cnt=0;
        }

        for(it=v[nod].begin();it!=v[nod].end();++it)
            if(!use[(*it).first]&&(D[(*it).first]>(*it).second||D[(*it).first]==-1))
            {
                D[(*it).first]=(*it).second;
                T[(*it).first]=nod;
                H[++cnt]=(*it).first;
                pos[(*it).first]=cnt;
                HeapUp(cnt);
            }
    }

    out.open("apm.out");

    M=0;
    for(int i=2;i<=N;i++) M+=D[i];

    out<<M<<'\n'<<N-1<<'\n';

    for(int i=2;i<=N;i++)
        out<<i<<' '<<T[i]<<'\n';

    out.close();

    return 0;
}