#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

struct Trio{
    int x, y, w;
};

vector<Trio> L;
vector<int> tata(200001, 0);
int cost;
vector<pair<int, int>> apcm;
vector<int> h(200001, 1);

int Find(int node)
{
    while(node != tata[node])
        node = tata[node];

    return node;
}

void Union(int x, int y)
{
    int p1 = Find(x), p2 = Find(y);

    if(h[p1] > h[p2])
        tata[p2] = p1;
    else if(h[p2] < h[p1])
            tata[p1] = p2;
        else 
        {
            tata[p1] = p2;
            h[p2] ++;
        }
}

int main()
{
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        int x, y, w; 

        fin >> x >> y >> w;

        L.push_back({x, y, w});
    }

    sort(L.begin(), L.end(), [] (const Trio a, const Trio b)
    {
        return a.w < b.w;
    });

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

    for(auto l: L)
    {
        if(Find(l.x) != Find(l.y))
        {
            apcm.push_back({l.x, l.y});
            Union(l.x, l.y);
            cost += l.w;
        }
    }

    fout << cost << '\n';
    fout << apcm.size() << '\n';
    for(auto m: apcm)
    {
        fout << m.first << ' ' << m.second << '\n';
    }

    return 0;
}