#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 200000;

int n, m;

struct Edge
{
    int x, y, c;
};

inline bool cmp(const Edge &a, const Edge &b)
    {
        if(a.c == b.c)
            return a.x < b.x;
        return a.c < b.c;
    }

struct Parent
{
    int root, siz;
}p[NMAX + 1];

vector <Edge> v, fina;

struct APM
{
    int Parent(int x)
    {
        if(p[x].root == x)
            return x;
        p[x].root = Parent(p[p[x].root].root);
        return p[x].root;
    }

    void Unite(int x, int y)
    {
        x = Parent(x);
        y = Parent(y);
        if(p[x].siz < p[y].siz)
        {
            p[x].root = p[y].root;
            p[x].siz += p[y].siz;
        }
        else
        {
            p[y].root = p[x].root;
            p[y].siz += p[x].siz;
        }
    }
};

APM apm;

int main()
{
    int xx, yy, cc;
    long long s = 0;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> xx >> yy >> cc;
        v.push_back({xx, yy, cc});
    }

    for(int i = 1; i <= n; i++)
        p[i] = {i, 1};

    sort(v.begin(), v.end(), cmp);

    for(int i = 0; i < m; i++)
        if(apm.Parent(v[i].x) != apm.Parent(v[i].y))
        {
            apm.Unite(v[i].x, v[i].y);
            fina.push_back(v[i]);
        }

    for(int i = 0; i < fina.size(); i++)
        s += fina[i].c;

    fout << s << '\n' << fina.size() << '\n';

    for(int i = 0; i < fina.size(); i++)
        fout << fina[i].x << ' ' << fina[i].y <<'\n';
    return 0;
}