#include <fstream>
#include <queue>
using namespace std;

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

class val_heap
{
public:
    int cost_muchie, nr_nod, coming_from;
    bool operator<(const val_heap &x) const
    {
        return cost_muchie > x.cost_muchie;
    }
};

vector<val_heap> G[200005];
vector<int> capete_muchie[200005];
priority_queue<val_heap> min_heap;
long long N, M, cost_total, nr_muchii;
bool vizitat[200005];

void mst()
{
    val_heap root;
    root.cost_muchie = 0;
    root.nr_nod = 1;
    root.coming_from = 1;
    min_heap.push(root);
    while (!min_heap.empty())
    {
        while (!min_heap.empty() && vizitat[min_heap.top().nr_nod])
            min_heap.pop();
        if (min_heap.empty())
            break;
        val_heap nod = min_heap.top();
        nr_muchii++;
        capete_muchie[nod.coming_from].push_back(nod.nr_nod);
        min_heap.pop();
        cost_total += nod.cost_muchie;
        vizitat[nod.nr_nod] = true;
        for (int i = 0; i < G[nod.nr_nod].size(); i++)
        {
            min_heap.push(G[nod.nr_nod][i]);
        }
    }
}

int main()
{
    int X, Y, C;
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        fin >> X >> Y >> C;
        val_heap nod;
        nod.cost_muchie = C;
        nod.nr_nod = Y;
        nod.coming_from = X;
        G[X].push_back(nod);
        nod.nr_nod = X;
        nod.coming_from = Y;
        G[Y].push_back(nod);
    }
    mst();
    fout << cost_total << "\n"
         << nr_muchii - 1 << "\n";
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= capete_muchie[i].size(); j++)
        {
            if (i != 1 || j != 1)
            fout << i << " " << j << "\n";
        }
    }
    return 0;
}