#include <cstdio>
#include <algorithm>
#include <stack>

#define NMAX 200007
#define in "apm.in"
#define out "apm.out"

using namespace std;
int n, m, tata[NMAX], sum;
struct muchie
{
    int x;
    int y;
    int cost;
} v[(NMAX<<1)];
stack <int> sol;

bool comp(const muchie &a, const muchie &b)
{
    return (a.cost < b.cost);
}

int root(const int &key)
{
    int rkey = key, aux;
    while(tata[rkey] > 0)
        rkey = tata[rkey];
    aux = key;
    while(tata[aux] > 0)
    {
        int tmp = aux;
        aux = tata[aux];
        tata[tmp] = rkey;
    }
    return rkey;
}
void unit(const int &a, const int &b)
{
    int rx = root(a), ry = root(b);
    if(tata[rx] < tata[ry])
    {
        tata[rx] += tata[ry];
        tata[ry] = rx;
        return ;
    }
    tata[ry] += tata[rx];
    tata[rx] = ry;
    return ;
}
int query(const int &a, const int &b)
{
    int rx = root(a), ry = root(b);
    return (rx == ry);
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; ++i)
    {
        scanf("%d %d %d", &v[i].x, &v[i].y, &v[i].cost);
    }
    sort(v+1, v+m+1, comp);
    for(int i = 1; i<= m; ++i)
    {
        if(query(v[i].x, v[i].y)) continue;
        sol.push(i);
        sum += v[i].cost;
        unit(v[i].x, v[i].y);
    }
    printf("%d\n%d\n", sum, n-1);
    while(!sol.empty())
    {
        int topp = sol.top();
        sol.pop();
        printf("%d %d\n", v[topp].x, v[topp].y);
    }
    return 0;
}