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

using namespace std;
const int N = 2e5 + 1;

int t[N], rang[N], n, m, totalcost;

struct muchie
{
    int x, y, c;
    bool operator < (const muchie& other) const
    {
        return (this -> c < other.c);
    }
}muchii[2 * N];

int Find(int x)
{
    if (t[x] == 0)
        return x;
    int y = Find(t[x]);
    t[x] = y;
    return y;
}

void Union(int x, int y)
{
    if (rang[x] > rang[y])
        swap(x, y);
    t[x] = y;
    if (rang[x] == rang[y]) rang[y]++;
}

vector <pair <int, int> > sol;

void Kruskal()
{
    sort(muchii + 1, muchii + m + 1);
    for (int i = 1; i <= m; i++)
    {
        int x = Find(muchii[i].x);
        int y = Find(muchii[i].y);
        if (x != y)
        {
            Union(x, y);
            totalcost += muchii[i].c;
            sol.push_back({muchii[i].x, muchii[i].y});
        }
        if (sol.size() == n - 1) break;
    }
}

void Write()
{
    ofstream fout ("apm.out");
    fout << totalcost << "\n" << n - 1 << "\n";
    for (int i = 0; i < sol.size(); i++)
        fout << sol[i].first << " " << sol[i].second << "\n";
    fout.close();
}

int main() {
    ifstream fin("apm.in");
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].c;
    Kruskal();
    Write();
    fin.close();
}