#include <cstdio>
#include <vector>
#include <utility>
#define Nmax 200001
#define INF 999999999

using namespace std;
FILE *f1 = fopen("apm.in","r");
FILE *f2 = fopen("apm.out","w");
int h[Nmax],n,m,u,v,c,i,nr,nod,S,t[Nmax],d[Nmax],pos[Nmax];
vector <pair <int,int> > a[Nmax],sol;

void swap(int i,int j)
{int aux;
aux=h[i];h[i]=h[j];h[j]=aux;
pos[h[i]]=i;pos[h[j]]=j;
}

void push(int x)
{while (x/2 && d[h[x]]<d[h[x/2]])
{swap(x,x/2);
x=x/2;
}
}


void pop(int x,int m)
{int y=0;
while (x!=y)
{y=x;
if (y*2<=m && d[h[x]]>d[h[y*2]]) x=2*y;
if (y*2+1<=m && d[h[x]]>d[h[y*2+1]]) x=2*y+1;
swap(x,y);
}
}

int Ext()
{int v=h[1];
swap(1,nr);
nr--;
pop(1,nr);
pos[v]=0;
return v;
}

int main()
{fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d%d",&u,&v,&c);a[u].push_back(make_pair(v,c));a[v].push_back(make_pair(u,c));}
nr=0;
for (i=2;i<=n;i++) d[i]=INF;
for (i=0;i<a[1].size();i++) {d[a[1][i].first]=a[1][i].second;t[a[1][i].first]=1;}
for (i=2;i<=n;i++) {h[++nr]=i;pos[i]=nr;push(nr);}

while (nr)
{nod=Ext();
S+=d[nod];
sol.push_back(make_pair(t[nod],nod));
for (i=0;i<(int)a[nod].size();i++)
{c=a[nod][i].second;
if (d[a[nod][i].first]>c)
{d[a[nod][i].first]=c;
t[a[nod][i].first]=nod;
push(pos[a[nod][i].first]);
}
}
}
fprintf(f2,"%d\n%d\n",S,sol.size());
for (i=0;i<(int)sol.size();i++) fprintf(f2,"%d %d\n",sol[i].first,sol[i].second);
    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.