#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 200002;
const int M = 400002;
int n, m, sol_cost;
int arb[N];
struct muchie
{
    int x, y, c;
} v[M];
vector <muchie> sol;

inline bool cmp (muchie a, muchie b)
{
    return a.c < b.c;
}

void read ()
{
    FILE *fis = fopen ("apm.in", "r");
    fscanf(fis, "%d %d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        arb[i] = i;
    for (int i = 1, x, y, c; i <= m; i ++ )
    {
        fscanf(fis, "%d %d %d", &x, &y, &c);
        v[i].x = x, v[i].y = y, v[i].c = c;
    }
    fclose(fis);
}

void sol_edge(muchie x)
{
    sol_cost += x.c;
    sol.push_back(x);
}

int find_set(int nod)
{
    if ( arb[nod] == nod ) return nod;
    return ( arb[nod] = find_set(arb[nod]) );
}

void merge_set (int x, int y)
{
    arb[find_set(x)] = find_set(y);
}

void solve ()
{
    sort(v+1, v+m+1, cmp);
    for (int i = 1; i <= m; i ++ )
    {
        if ( find_set(v[i].x) != find_set(v[i].y) )
        {
            sol_edge(v[i]);
            merge_set(v[i].x, v[i].y);
        }
    }
}

void write ()
{
    FILE *fis2 = fopen ("apm.out", "w");
    fprintf(fis2, "%d\n%d\n", sol_cost, sol.size());
    for (int i = 0; i < sol.size(); i ++ )
        fprintf(fis2, "%d %d\n", sol[i].y, sol[i].x);
    fclose(fis2);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}