#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(WHATEVER) for(int i = 1; i <= WHATEVER; ++ i)

/// INPUT / OUTPUT
const string problem = "apm";
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");

/// STRUCTURES
struct graph
{
    int node1, node2, cost;
};

/// GLOBAL VARIABLES
const ll NMAX = 2e5 + 5, MOD = 1e9 + 7, INF = 1e9;
int n, m, muchii;
int parent[NMAX], sets[NMAX];
graph g[NMAX], sol[NMAX];

inline bool comp(const graph &x, const graph &y)
{
    return x.cost < y.cost;
}

inline int Find(int x)
{
    if(parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]);
}

inline void Union(int x, int y)
{
    int parx = Find(x), pary = Find(y);
    if(sets[parx] < sets[pary])
    {
        swap(parx, pary);
        swap(x, y);
    }
    sets[parx] += sets[pary];
    parent[pary] = parx;
}

/// READING THE INPUT
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n >> m;

    for(int i = 1; i <= m; ++ i)
        fin >> g[i].node1 >> g[i].node2 >> g[i].cost;
    sort(g + 1, g + m + 1, comp);
    int cost = 0, k = 1;
    for(int i = 1; i <= m; ++ i)
    {
        parent[i] = i;
        sets[i] = 1;
    }

    for(int i = 1; i <= m; ++ i)
    {
        int x = g[i].node1;
        int y = g[i].node2;
        if(Find(x) != Find(y))
        {
            Union(x, y);
            cost += g[i].cost;
            sol[k++] = g[i];
            muchii++;
        }
    }
    fout << cost << '\n' << muchii << '\n';
    for(int i = 1; i < n; ++ i)
        fout << sol[i].node1 << ' ' << sol[i].node2 << '\n';
}