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

#define MAX 101

using namespace std;

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

int main()
{
    int M,N,x,y,c,min,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(use,0,sizeof(use));
    memset(T,0,sizeof(T));
    use[1]=1;

    for(it=v[1].begin();it!=v[1].end();it++)
        D[(*it).first]=(*it).second,T[(*it).first]=1;

    while(1)
    {
        min=-1;

        for(int i=1;i<=N;i++)
            if(((D[i]<min&&D[i]!=-1)||min==-1)&&!use[i])
            {
                min=D[i];
                nod=i;
            }

        if(min==-1) break;

        use[nod]=1;

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

    out.open("apm.out");

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

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

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

    out.close();

    return 0;
}