#include <cstdio>
#include <algorithm>
#include <vector>

#define FILEIN "apm.in"
#define FILEOUT "apm.out"
#define NMAX 200000
#define MMAX 400000

using namespace std;


struct edge {
    int x;
    int y;
    int c;
};


int N, M;
int Set[NMAX];
edge V[MMAX];
vector<edge> Sol;


int comp_edge(edge A, edge B)
{
    return A.c < B.c;
}

edge make_edge(int x, int y, int c)
{
    edge ret;

    ret.x = x;
    ret.y = y;
    ret.c = c;

    return ret;
}

int sol_cost = 0;

void sol_edge(edge X)
{
    Sol.push_back(X);
    sol_cost += X.c;
}

int find_set(int node)
{
    if (Set[node] == node) return node;

    return (Set[node] = find_set(Set[node]));
}

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

int main()
{
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &M);

    for (int i = 1; i <= N; i++)
        Set[i] = i;

    for (int i = 1, x, y, c; i <= M; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        V[i] = make_edge(x,y,c);
    }

    sort(V+1, V+M+1, comp_edge);

    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);
        }
    }

    printf("%d\n%d\n", sol_cost, Sol.size());
    for (int i = 0; i < Sol.size(); i++)
        printf("%d %d\n", Sol[i].x, Sol[i].y);

    return 0;
}