#include <cstdio>
#define NMAX 400005
#define pb push_back
#include <algorithm>
#include <vector>
using namespace std;

FILE *f = freopen("apm.in", "r", stdin);
FILE *g = freopen("apm.out", "w", stdout);
int Father[NMAX];
struct ans{
    int x,y;
};
vector <ans> ANS;
int x[NMAX], y[NMAX], cost[NMAX], ind[NMAX], N, M, costsol;
int find_(int x)
{
    while(x != Father[x])
        x = Father[x];
}
void unite_(int x, int y)
{
    Father[find_(x)] = find_(y);
}
bool cmp(int x, int y)
{
    return cost[x] < cost[y];
}
void read()
{
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=M; i++)
    {
        scanf("%d%d%d", &x[i], &y[i], &cost[i]);
        ind[i] = i;
    }
    sort(ind + 1, ind + M + 1, cmp);
    for(int i = 1; i<=N; i++) Father[i] = i;
}
void solve()
{
    for(int i = 1; i<=M; i++)
    {
        if(find_(x[ind[i]]) != find_(y[ind[i]])) {
            costsol += cost[ind[i]];
            unite_(x[ind[i]], y[ind[i]]);
            ans ras;
            ras.x = x[ind[i]];
            ras.y = y[ind[i]];
            ANS.pb(ras);
        }
    }
}
void write()
{
    printf("%d\n%d\n", costsol, ANS.size());
    for(int i = 0; i<ANS.size(); i++)
        printf("%d %d\n", ANS[i].x, ANS[i].y);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}