/*
Arbore partial de cost minim
Se da un graf conex neorientat G cu N noduri si M muchii, fiecare muchie avand asociat un cost. Se cere sa se determine un subgraf care cuprinde toate nodurile si o parte din muchii, astfel incat subgraful determinat sa aiba structura de arbore si suma costurilor muchiilor care il formeaza sa fie minim posibila. Subgraful cu proprietatile de mai sus se va numi arbore partial de cost minim pentru graful dat.

Date de intrare
Fisierul de intrare apm.in va contine pe prima linie numerele N si M, separate printr-un spatiu. Pe urmatoarele M linii se vor gasi muchiile grafului sub forma X Y C, cu semnificatia ca exista muchie neorientata intre X si Y de cost C.

Date de ieşire
Fisierul de iesire apm.out va contine pe prima linie costul arborelui partial de cost minim. Pe a doua linie se va gasi numarul de muchii din arborele partial selectat. Fiecare din urmatoarele linii, pana la sfarsitul fisierului de iesire, va contine cate doua numere naturale, capetele unei muchii ce apartine arborelui solutie. Muchiile pot fi afisate in orice ordine. Daca sunt mai multe solutii corecte se poate afisa oricare.

Restricţii
1 ≤ N ≤ 200 000
1 ≤ M ≤ 400 000
-1 000 ≤ C ≤ 1 000
Pentru 20% din teste N, M ≤ 20
Pentru inca 20% din teste N ≤ 800 si M ≤ 1 500
*/
// Algoritmul lui Prim
#include <bits/stdc++.h>
#define NMAX 200005

using namespace std;

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

struct A
{
    int cost, dest;
};

struct B
{
    int x, y;
};

multimap < int, B > a;
vector < A > v[NMAX];
vector < B > r;

int main()
{
    vector < A > ::iterator it;
    A el;
    int n, m, x, y, z, nr, s = 0;
    bool viz[NMAX] = {0};

    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y >> z;
        v[x].push_back({z, y});
        v[y].push_back({z, x});
    }

    nr = 1;
    viz[1] = 1;
    for(it = v[1].begin(); it != v[1].end(); it++) a.insert({(*it).cost, { 1, (*it).dest} });
    while(nr < n)
    {
        x = a.begin()->second.y;
        if(viz[x] != 0) a.erase(a.begin());
        else
        {
            s += a.begin()->first;
            r.push_back({a.begin()->second.x, a.begin()->second.y});
            a.erase(a.begin());

            nr++;
            viz[x] = 1;

            for(it = v[x].begin(); it != v[x].end(); it++ ) if(viz[(*it).dest] == 0) a.insert({(*it).cost, {x, (*it).dest}});
        }
    }

    fout << s << '\n' << n - 1 << '\n';
    for(auto it: r) fout << it.x << ' ' << it.y << '\n';

    return 0;
}

/*
IN1:
9 14
1 2 10
1 3 -11
2 4 11
2 5 11
5 6 13
3 4 10
4 6 12
4 7 5
3 7 4
3 8 5
8 7 5
8 9 4
9 7 3
6 7 11

OUT1;
37
8
3 1
7 9
7 3
9 8
7 4
2 1
5 2
7 6


IN2:
3 3
1 2 -3
2 3 -4
3 1 -5

OUT2:
-9
2
1 3
3 2
*/

//Algoritmul lui Kruskal
/*
#include <bits/stdc++.h>
#define NMAX 200005

using namespace std;

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

struct A
{
    int x, y, cost;
};

struct B
{
    int x, y;
};

struct crt
{
    bool operator()(A a, A b)
    {
        if(a.cost < b.cost) return 1;
        else return 0;
    }
};

multiset < A, crt > a;
vector < B > r;
int t[NMAX], lg[NMAX];

void uneste(int x, int y);
int radacina(int x);

int main()
{
    multiset < A, crt > :: iterator it;
    vector < B > ::iterator itt;
    A el;
    int n, m, x, y, z, i, s = 0;

    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y >> z;
        a.insert({x, y, z});
    }

    for(i = 1; i <= n; i++) t[i] = i, lg[i] = 1;
    for(it = a.begin(); it != a.end(); it++)
    {
        x = radacina((*it).x);
        y = radacina((*it).y);

        if(x != y)
        {
            uneste(x, y);
            s += (*it).cost;
            r.push_back({(*it).x, (*it).y});
        }
    }

    fout << s << '\n' << n - 1 << '\n';
    for(itt = r.begin(); itt != r.end(); itt++) fout << (*itt).x << ' ' << (*itt).y << '\n';

    return 0;
}

void uneste(int x, int y)
{
    if(lg[x] < lg[y]) lg[y] += lg[x], t[x] = y;
    else lg[x] += lg[y], t[y] = x;
}

int radacina(int x)
{
    if(t[x] != x) t[x] = radacina(t[x]);

    return t[x];
}
*/