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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout

struct node
{
    int parent;
    int size;
};

vector<node> v;

bool initialize(int N)
{
    v.resize(N + 1);

    for(int i = 1; i <= N; i++)
    {
        v[i].parent = i;
        v[i].size   = 1;
    }

    return 0;
}

int find_root(int i)
{
    if(v[i].parent == i)
        return i;

    v[i].parent = find_root(v[i].parent);

    return v[i].parent;
}

bool union_make(int x, int y)
{
    int xroot = find_root(x);
    int yroot = find_root(y);

    if(xroot == yroot)
        return 0;

    if(v[xroot].size < v[yroot].size)
        swap(xroot, yroot);

    //xroot.size > yrooy.size

    v[yroot].parent = xroot;
    v[xroot].size  += v[yroot].size;

    return 0;
}

int N, M;
vector<pair<int, pair<int, int>>> m;

int main()
{
    cin >> N >> M;

    initialize(N);

    m.resize(M);

    int a, b, c;
    for(int i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        m[i] = {c, {a, b}};
    }

    sort(m.begin(), m.end());

    int S = 0;

    vector<int> rez;

    for(int i = 0; i < M; i++)
    {
        int a = m[i].second.first;
        int b = m[i].second.second;
        int aroot = find_root(a);
        int broot = find_root(b);
        if(aroot != broot)
        {
            union_make(a, b);
            S += m[i].first;
            rez.push_back(i);
            if(rez.size() == N - 1)
                break;
        }
    }

    cout << S << '\n' << rez.size() << '\n';

    for(auto &e : rez)
        cout << m[e].second.first << ' ' << m[e].second.second << '\n';

    return 0;
}