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

using namespace std;

struct much
{
    int a, b, c;

    much(int _a, int _b, int _c)
        : a(_a), b(_b), c(_c) {}

    bool operator<(const much& m)
    {
        return c < m.c;
    }
};

struct uf_type
{
    int tata[200001];
    int size[200001];

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

    int find(int x)
    {
        vector<int> path;
        while(x != tata[x])
        {
            path.push_back(x);
            x = tata[x];
        }

        for(const auto& y : path)
            tata[y] = x;

        return x;
    }

    void sunion(int x, int y)
    {
        int rx = find(x), ry = find(y);
        
        if(rx != ry)
        {
            if(size[rx] < size[ry])
            {
                tata[rx] = ry;
                size[ry] += size[rx];
            }
            else
            {
                tata[ry] = rx;
                size[rx] += size[ry];
            }
        }
    }
};

int N, M, C = 0;
vector<much> E;
vector<much> MST;

void kruskal_mst()
{
    uf_type uf(N + 1);

    for(const auto& e : E)
    {
        if(uf.find(e.a) != uf.find(e.b))
        {
            C += e.c;
            MST.push_back(e);
            uf.sunion(e.a, e.b);
        }

        if(MST.size() >= N - 1)
            break;
    }
}

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

    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        E.push_back(much(a, b, c));
    }

    sort(E.begin(), E.end());
    kruskal_mst();

    fout << C << '\n' << N - 1 << '\n';
    for(const auto& e : MST)
        fout << e.a << ' ' << e.b << '\n';

    fin.close();
    fout.close();

    return 0;
}