#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];
vector <pair <int,int> > a[Nmax],sol;

int cost(int x,int y)
{int i;
for (i=0;i<(int)a[x].size();i++)
    if (a[x][i].first==y) return a[x][i].second;
return INF;
}
void CombHeap(int i,int n)
{int v=h[i],fiu=2*i,tata=i;
while (fiu<=n)
{if (fiu<n && d[h[fiu]]>d[h[fiu+1]]) fiu++;
if (d[v]>d[h[fiu]])
{h[tata]=h[fiu];
tata=fiu;
fiu=fiu*2;
}
else fiu=n+1;
}
h[tata]=v;
}

void Creare(int n)
{int i;
for (i=n/2;i>=1;i--) CombHeap(i,n);
}

int Ext(int &n)
{int v=h[1];
h[1]=h[n--];
CombHeap(1,n);
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=n-1;
for (i=2;i<=n;i++) {h[i-1]=i;d[i]=cost(1,i);if (d[i]!=INF) t[i]=1;}

while (nr)
{Creare(nr);
nod=Ext(nr);
S+=d[nod];
sol.push_back(make_pair(t[nod],nod));
for (i=0;i<(int)a[nod].size();i++)
{c=cost(nod,a[nod][i].first);
if (d[a[nod][i].first]>c)
{d[a[nod][i].first]=c;
t[a[nod][i].first]=nod;
}
}
}
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.