#include <fstream>
#include <vector>
#define NMAX 100
#define INF 100000;
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
void citire();
void prim(int x);
struct muchie {int vf,cost;};
vector <muchie> C[NMAX];
int n,m,pre[NMAX],M[NMAX],Cmin[NMAX];
int main()
{
    int i,s=0;
    citire();
    prim(1);
    for(i=1;i<=n;i++) s+=Cmin[i];
    fout<<s<<"\n"<<n-1<<"\n";
    for(i=2;i<=n;i++)
        fout<<i<<" "<<pre[i]<<"\n";
}
void citire()
{
    int a,b,c,i;
    muchie aux;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        aux.vf=b;aux.cost=c;
        C[a].push_back(aux);
        aux.vf=a;
        C[b].push_back(aux);
    }
}
void prim(int x)
{
    int i,vfmin,minim,j;
    for(i=1;i<=n;i++) {Cmin[i]=INF;pre[i]=x;}
    M[x]=1; Cmin[x]=0;
    for(j=0;j<C[x].size();j++)
    {
          Cmin[C[x][j].vf]=C[x][j].cost;
          pre[C[x][j].vf]=x;
    }

    for(i=1;i<n;i++)
    {
        minim=INF+1;
        for(j=1;j<=n;j++)
            if(Cmin[j]<minim&&M[j]==0)
            {
                minim=Cmin[j];
                vfmin=j;
            }
        M[vfmin]=1;
        for(j=0;j<C[vfmin].size();j++)
            if(Cmin[C[vfmin][j].vf]>C[vfmin][j].cost&&M[C[vfmin][j].vf]==0)
            {
                Cmin[C[vfmin][j].vf]=C[vfmin][j].cost;
                pre[C[vfmin][j].vf]=vfmin;
            }

    }
}