#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream f ("apm.in");
ofstream g ("apm.out");

struct punct
{
    int x, y, c;
}u[400001], sol[200010];

int n, m, x, y, c, arr[200010], len[200010], k, i, ct;

int cmp (punct a, punct b)
{
    return (a.c<b.c);
}

int root (int x)
{
    while (arr[x]!=x)
    {
        arr[x]=arr[arr[x]];
        x=arr[x];
    }
    return x;
}

bool Find (int x, int y)
{
    if (root(x)==root(y)) return true;
    return false;
}

void Union (int a, int b)
{
    int root_a=root(a);
    int root_b=root(b);

    if (len[root_a]>len[root_b])
    {
        arr[root_b]=root_a;
        len[root_a]+=len[root_b];
    }
    else
    {
        arr[root_a]=root_b;
        len[root_b]+=root_a;
    }
}

int main ()
{
    f >> n >> m;

    for (int i=1; i<=n; i++)
    {
        arr[i]=i;
        len[i]=1;
    }

    for (int i=1; i<=m; i++)
    {
        f >> u[i].x >> u[i].y >> u[i].c;
    }

    sort(u+1, u+m+1, cmp);
    i=1;;

    while (k<n-1 && i<=m)
    {
        if (!Find(u[i].x, u[i].y)){
            Union(u[i].x, u[i].y);
            k++;
//            g << u[i].x << " " << u[i].y << '\n';
            sol[k]=u[i];
//            g <<sol[k].x << " " << sol[k].y << '\n' << '\n';
            ct+=u[i].c;
        }
        i++;
    }

    g << ct << '\n' << k << '\n';
    for (int i=1; i<=k; i++)
        g << sol[i].x << " " << sol[i].y << '\n';
    return 0;

}