#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

#define NEGINF -32000

using namespace std;


struct sEdges{int x,y,c;};
int n,m;
vector<sEdges> costs;

class CompareEdges
{
    public:
        bool operator() (const sEdges& x, const sEdges& y) const
        {
            return x.c < y.c;
        }
};

void citire()
{
    freopen("krushkal.in","r",stdin);
    freopen("krushkal.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y,c;
    for (int i=1;i<=m;i++)
    {
        scanf("%d %d %d\n",&x,&y,&c);
        sEdges k;
        k.x = x;
        k.y = y;
        k.c = c;
        costs.push_back(k);
    }
}

void rezolva()
{
    int *vertex;
    vertex = new int[n+1];
    for (int i=1;i<=n;i++)
    vertex[i]=i;
    make_heap(costs.begin(),costs.end(), CompareEdges());
    sort_heap(costs.begin(),costs.end(), CompareEdges());
    for (int i=0;i<m;i++)
    {
        sEdges k = costs[i];
        if (vertex[k.x]!=vertex[k.y])
        {
            int vX = vertex[k.x];
            int vY = vertex[k.y];
            for (int j=1;j<=n;j++)
                if(vertex[j]==vX || vertex[j]==vY)
                    vertex[j]=vY;
        }
        else
            costs[i].c=NEGINF;
    }
}

void afisare()
{
    int nr=0,sum=0;
    int a[10000][2];
    for (int i=0;i<m;i++)
    {
        if (costs[i].c!=NEGINF)
        {
            a[i][1]=costs[i].y;
            a[i][2]=costs[i].x;
            nr++;
            sum+=costs[i].c;
        }
    }
     printf("%d",sum);
     printf("\n");
     printf("%d",nr);
     printf("\n");
     for (int i=0;i<m;i++)
     {
         if(a[i][1]!=0 && a[i][2]!=0)
        {
            printf("%d %d",a[i][1],a[i][2]);
            printf("\n");
        }
     }
}


int main()
{
    citire();
    rezolva();
    afisare();
    return 0;
}