#include <bits/stdc++.h>
using namespace std;

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

struct Patru
{
    int x, y, c, viz;

    Patru(int x_, int y_, int c_)
    {
        x = x_;
        y = y_;
        c = c_;
        viz = 0;
    }

    bool operator<(const Patru e) const
    {
        return c < e.c;
    }
};

int n, m;
vector<Patru> v;
int t[100005];

int FindRoot(int x)
{
    int y, rad = x;
    while (t[rad] != 0)
        rad = t[rad];
    while (x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}

int main()
{
    int i, j, c, Cost, Cnt;
    fin >> n >> m;
    while (m--)
    {
        fin >> i >> j >> c;
        auto X = Patru(i, j, c);
        v.push_back(X);
    }
    sort(v.begin(), v.end());
    Cnt = Cost = 0;
    for (auto &w : v)
    {
        i = w.x; j = w.y; c = w.c;
        i = FindRoot(i); j = FindRoot(j);
        if (i != j)
        {
            Cnt++;
            Cost += c;
            t[j] = i;
            w.viz = 1;
        }
    }
    fout << Cost << "\n" << Cnt << "\n";;
    for (auto w : v)
        if (w.viz == 1)
            fout << w.x << " " << w.y << "\n";
    return 0;
}