#include<cstdio>
#include<algorithm>
using namespace std;
int N,M,i,Father[400005],X,Y,C,Cost,Sol;
struct Muchie {int X,Y,C;} V[400005];
struct Solutie {int X,Y;} S[400005];
bool cmp(Muchie A, Muchie B) {return A.C<B.C;}
int Find(int X)
{
    if(Father[X]!=X) Father[X]=Find(Father[X]);
    return Father[X];
}
void Unite(int X,int Y)
{
    Father[X]=Y;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++) scanf("%d%d%d",&V[i].X,&V[i].Y,&V[i].C);
    sort(V+1,V+M+1,cmp);
    for(i=1;i<=N;i++) Father[i]=i;
    for(i=1;i<=M;i++)
    {
        X=V[i].X; Y=V[i].Y; C=V[i].C;
        if(Find(X)==Find(Y)) continue;
        Cost+=C; S[++Sol].X=X; S[Sol].Y=Y;
        Unite(Find(X),Find(Y));
    }
    printf("%d\n%d\n",Cost,Sol);
    for(i=1;i<=Sol;i++) printf("%d %d\n",S[i].X,S[i].Y);
    return 0;
}