#include <stdio.h>
#include <fstream>
#include <algorithm>

using namespace std;

int N,M,P[400001],Ter[200001],Graf[200001],V[200001];
struct muchie {int x,y,c;};
muchie mc[400001];

bool cmp(int a,int b) {return mc[a].c<mc[b].c;}

int search(int a)
{
    int w;
    for(w=a;Ter[w]!=w; w=Ter[w]);
        return w;
}
void combine(int a,int b)
{
    if(Graf[a]>Graf[b]) Ter[b]=a;
        else Ter[b]=a;
    if (Graf[a]==Graf[b]) Graf[b]++;
}
int main()
{
    FILE*f,*g;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    fscanf(f,"%d%d",&N,&M);
    int t=0,s=0;
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d",&mc[i].x);
        fscanf(f,"%d",&mc[i].y);
        fscanf(f,"%d",&mc[i].c);
        P[i]=i;
    }

    for(int i=1;i<=N;i++)
    {
        Graf[i]=1;
        Ter[i]=i;
    }

    sort(P+1,P+M+1,cmp);

    for(int i=1;i<=M;i++)
    {
        int a,b;
        a=search(mc[P[i]].x);
        b=search(mc[P[i]].y);
        if(a!=b) {combine(a,b); s=s+mc[P[i]].c; t++; V[t]=P[i];}

    }
    fprintf(g,"%d\n%d\n",s,t);
    for(int i=1;i<=t;i++)
    {
        fprintf(g,"%d %d\n",mc[V[i]].x,mc[V[i]].y);
    }


    return 0;
}