#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 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 usable[MMAX + 1]; //0 daca nu pot sa folosesc acea muchie,
//1 daca o pot folosi in realizarea componentelor conexe

int vecin(int ind, int nod)
{
    if (edges[ind].a == nod)
        return edges[ind].b;
    return edges[ind].a;
}

void dfs(int nod, int cnt)
{
    viz[nod] = cnt;
    for (int ind : g[nod])
    {
        int v = vecin(ind, nod);
        if (!viz[v] and usable[ind])
        {
            dfs(v, cnt);
        }
    }
}

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;
        g[edges[i].a].push_back(i);
        g[edges[i].b].push_back(i);
    }
    for (i = 1; i <= n; i++)
        viz[i] = i;
    bool done = 0;
    while (!done)
    {
        done = 1;
        for (i = 1; i <= n; i++)
            mn[i] = 0;
        for (i = 1; i <= m; i++)
            if (viz[edges[i].a] != viz[edges[i].b])
            {
                done = 0;
                schimba(viz[edges[i].a], i);
                schimba(viz[edges[i].b], i);
            }
        for (i = 1; i <= n; i++)
        {
            if (mn[i] != 0)
            {
                usable[mn[i]] = 1;
            }
            viz[i] = 0;
        }
        int cnt = 0;
        for (i = 1; i <= n; i++)
            if (!viz[i])
            {
                cnt++;
                dfs(i, cnt);
            }
    }
    int ans = 0;
    for (i = 1; i <= m; i++)
        if (usable[i])
            ans += edges[i].c;
    cout << ans << "\n" << n - 1 << "\n";
    for (i = 1; i <= m; i++)
        if (usable[i])
            cout << edges[i].a << " " << edges[i].b << '\n';
}