#include <stdio.h>
#include <iostream>
using namespace std;
int n,m;
int h[200020], t[200020];
int viz[200001];
struct muchie
{
    int x, y, cost;
};

muchie v[200020];
int FindSet(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
void UnionSet(int x, int y)
{
    if(h[x]==h[y])
    {
        t[y]=x;
        h[x]++;
    }
    else if (h[x]>h[y])
        t[y]=x;
    else t[x]=y;
}



int main()
{
    freopen("apm.in", "r",stdin);
    freopen("apm.out","w",stdout);
    int i;
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d", &v[i].x, &v[i].y, &v[i].cost);

    }
   int j;
   muchie aux;
   for(i=1;i<m;i++)
    for(j=i+1;j<=m;j++)
    if(v[i].cost>v[j].cost)
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }

    int k=0, tx, ty;
    for(i=1; i<=n; i++)
    {
        t[i]=i;
        h[i]=1;
    }
    int ve[200001], sum=0;
    for(i=1; i<=m && k<n-1; i++)
    {
        tx=v[i].x;
        ty=v[i].y;
        if(FindSet(t[tx])!=FindSet(t[ty]))
        {
            UnionSet(t[tx],t[ty]);
            ve[k]=i;
            k++;
            sum=v[i].cost +sum;
        }

        }
    printf("%d\n" ,  sum);
    printf("%d\n", n-1);


    for(i=0;i<k;i++)
        printf("%d %d\n", v[ve[i]].y, v[ve[i]].x);

    return 0;
}