#include <bits/stdc++.h>
#define NMAX 200008
#define MMAX 400008

using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct Muchie
{
    int x, y, z;
};

struct comparare
{
    bool operator() (const Muchie & a, const Muchie & b)
    {
        return a.z > b.z;
    }
};

int n, m, total, t[NMAX], h[NMAX], lgx, lgy;
priority_queue <Muchie, vector<Muchie>, comparare> H;
int solx[MMAX], soly[MMAX];
vector < pair <int, int> > sol;

int Find (int x);
void Union (int x, int y);

int main()
{
    ios_base::sync_with_stdio(0); fin.tie(0);
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        H.push({x, y, z});
    }

    Muchie M;
    int cnt = 0;
    while (cnt < n - 1)
    {
        M = H.top();
        H.pop();
        int c1 = Find(M.x);
        int c2 = Find(M.y);
        if (c1 != c2)
        {
            Union(c1, c2);
            total += M.z;
            cnt++;
            solx[++lgx] = M.x;
            soly[++lgy] = M.y;
        }
    }
    fout << total << '\n';
    fout << lgx << '\n';
    for (int i = 1; i <= lgx; i++)
        fout << solx[i] << ' ' << soly[i] << '\n';
    return 0;
}

int Find (int x)
{
    int root = x, aux;
    while (t[root])
        root = t[root];

    while (t[x])
    {
        aux = t[x];
        t[x] = root;
        x = aux;
    }
    return root;
}

void Union (int x, int y)
{
    if (h[x] < h[y])
        t[x] = y;
    else if (h[x] > h[y])
        t[y] = x;
    else
    {
        t[x] = y;
        h[y]++;
    }
}