#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 200011
#define MAXM 400011
#define TR(C, it) for (typeof (C.begin ()) it = C.begin (); it != C.end (); it++)
using namespace std;

int N, M;
vector <pair <pair <int, int>, pair <int, int> > > muchii;
pair <int, int> point[MAXN];

void Citire ()
{
    ifstream fin ("apm.in");
    fin >> N >> M;
    for (int i = 0, a, b, c; i < M; i++)
    {
        fin >> a >> b >> c;
        muchii.push_back (make_pair (make_pair (c, 0), (make_pair (a, b))));
    }
    for (int i = 1; i <= N; i++)
        point[i].second = 1;
    sort (muchii.begin (), muchii.end ());
}

int Parent (int nod)
{
    if (!point[nod].first) return nod;
    point[nod].first = Parent (point[nod].first);
    return point[nod].first;
}

void Merge_DDS (int x, int y)
{
    x = Parent (x);
    y = Parent (y);
    if (x == y) return;
    if (point[x].second > point[y].second) point[y].first = x, point[x].second += point[y].second;
    else point[x].first = y, point[y].second += point[x].second;
}

int Kruskal ()
{
    int val = 0;
    TR (muchii, it)
    {
        int x = it -> second.first;
        int y = it -> second.second;
        int cost = it -> first.first;
        if (Parent (x) != Parent (y)) Merge_DDS (x, y), val += cost, it -> first.second = 1;
    }
    return val;
}

void Scriere ()
{
    ofstream fout ("apm.out");
    int a = Kruskal ();
    fout << a << "\n" << N - 1 << "\n";
    TR (muchii, it)
        if (it -> first.second) fout << it -> second.first << " " << it -> second.second << "\n";
    fout.close ();
}

int main ()
{
    Citire ();
    Scriere ();
    return 0;
}