#include <fstream>
#include <cassert>
#include <climits>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

const int NMAX = 2e5;
const int MMAX = 4e5;
const int INF = 1001;

struct dsu
{
    int c[NMAX + 1];
    void init(int n)
    {
        int i;
        for (i = 1; i <= n; i++)
            c[i] = i;
    }
    int dad(int poz)
    {
        if (c[poz] == poz)
            return poz;
        c[poz] = dad(c[poz]);
        return c[poz];
    }
    void unite(int a, int b)
    {
        c[dad(a)] = dad(b);
    }
};

dsu ds;

struct muchie
{
    int a, b, c;
};

muchie edges[MMAX + 1];

vector <int> g[NMAX + 1];
int viz[NMAX + 1];
int mn[NMAX + 1];

void schimba(int comp, int ind)
{
    if (mn[comp] == 0)
        mn[comp] = ind;
    else if (edges[mn[comp]].c > edges[ind].c)
        mn[comp] = ind;
}

bool used[MMAX + 1];

signed main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m, i;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
    }
    ds.init(n);
    bool done = 0;
    int cnt = n;
    while (!done)
    {
        done = 1;
        for (i = 1; i <= cnt; i++)
            mn[i] = 0;
        for (i = 1; i <= m; i++)
            if (ds.dad(edges[i].a) != ds.dad(edges[i].b))
            {
                done = 0;
                schimba(ds.dad(edges[i].a), i);
                schimba(ds.dad(edges[i].b), i);
            }
        for (i = 1; i <= cnt; i++)
        {
            used[mn[i]] = 1;
            ds.unite(edges[mn[i]].a, edges[mn[i]].b);
        }
    }
    int ans = 0;
    for (i = 1; i <= m; i++)
        if (used[i])
            ans += edges[i].c;
    cout << ans << "\n" << n - 1 << "\n";
    for (i = 1; i <= m; i++)
        if (used[i])
            cout << edges[i].a << " " << edges[i].b << '\n';
}