#include <stdio.h>
#include <vector>
#define NMAX 200001
#define INF 10000000;
using namespace std;
//ifstream fin("apm.in");
//ofstream fout("apm.out");
FILE *fin,*fout;
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";
    fprintf(fout,"%d\n%d\n",s,n-1);
    for(i=2;i<=n;i++)
        fprintf(fout,"%d %d\n",i,pre[i]);
       // fout<<i<<" "<<pre[i]<<"\n";
}
void citire()
{
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    int a,b,c,i;
    muchie aux;
    //fin>>n>>m;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&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;
            }

    }
}