#include<stdio.h>
#include<algorithm>
#include <vector>
#define Nmax 200009
#define Mmax 400009
#define c first
#define x second.first
#define y second.second

using namespace std;

int X,Y,cost,n,m,i,T[Nmax],R[Nmax];
vector <pair<int,pair<int,int> > > a(Mmax),sol;

int tata(int a)
{
    if (a==T[a]) return a;
    return tata(T[a]);
}

void uneste(int X,int Y)
{
    if (R[X]>R[Y]) T[Y]=X;
        else T[X]=Y;
    if (R[X]==R[Y]) R[Y]++;

    sol.push_back(a[i]);
    cost+=a[i].c;
}

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",&a[i].x,&a[i].y,&a[i].c);
    sort(a.begin()+1,a.begin()+m+1);

    for (i=1;i<=n;i++)
    {
        T[i]=i;
        R[i]=1;
    }
    for (i=1;i<=m;i++)
    {
        X=tata(a[i].x);
        Y=tata(a[i].y);

        if (X==Y) continue;
            else uneste(X,Y);
    }
    printf("%d\n%d\n",cost,sol.size());
    for (i=0;i<sol.size();i++)
        printf("%d %d\n",sol[i].x,sol[i].y);
}