#include <cstdio>
#include <algorithm>

using namespace std;

struct nod
{
    int x,y,c;
} e[400005];

bool cmp (nod A, nod B )
{
    if ( A.c < B.c )
        return true;
    return false;
}

int n,m,l[400005],nr,i,p,q,j,cost;
pair <int, int> g[200005];
int main()
{
    //kruskal

    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", &e[i].x, &e[i].y, &e[i].c);
        l[i]=i;
    }

    sort (e+1, e+m+1, cmp);

    cost=0;
    i=1;
    nr=0;

    while (i<=m  && nr<n-1)
    {
        if (l[e[i].x]!=l[e[i].y])
        {
            cost+=e[i].c;
            nr++;
            p=l[e[i].x]; g[nr].first=e[i].x;
            q=l[e[i].y]; g[nr].second=e[i].y;
            for (j=1; j<=n; j++)
                if (l[j]==p) l[j]=q;
        }

        i++;

    }

    printf ("%d\n%d\n", cost, nr);
    for(i=1;i<=nr;i++)
        printf ("%d %d\n", g[i].first, g[i].second);

    return 0;
}