#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define nmax 200001
#define INF 999999999

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector <pair<int, int> > v[nmax];
vector <pair<int, int> > mfinale;
priority_queue <pair<int, pair<int, int> > > myheap;


int radacina(int tata[], int x)
{
    while (x != tata[x])
    {
        tata[x] = tata[tata[x]];
        x = tata[x];
    }
    return x;
}

void reuniune(int tata[], int l[], int x, int y)
{
    if (l[radacina(tata, x)] < l[radacina(tata, y)])
    {
        tata[radacina(tata, x)] = tata[radacina(tata, y)];
    }
    else
    {
        tata[radacina(tata, y)] = tata[radacina(tata, x)];
        l[radacina(tata, x)]++;
    }
}

bool diferite(int tata[], int l[], int x, int y)
{
    if (radacina(tata, x) == radacina(tata, y))
        return false;
    return true;
}

int main()
{
    int N, M, x, y, cost;
    f>>N>>M;

    vector <int> dist(N+1, nmax);
    vector <int> viz(N+1);
    int tata[N+1], l[N+1];
    for (int i = 1; i <= N; i++)
        tata[i] = i, l[i] = 1;

    for (int i = 1; i <= M; i++)
    {
        f>>x>>y>>cost;
        myheap.push(make_pair(-cost, make_pair(x, y)));
    }
    cost = 0;
    int nr_muchii = 0;

    while (!myheap.empty() && nr_muchii < N-1)
    {
        pair <int, pair<int, int> > it = myheap.top();
        int x = it.second.first;
        int y = it.second.second;
        myheap.pop();

        if (!diferite(tata, l, x, y))
            continue;

        reuniune(tata, l, x, y);

        cost -= it.first;
        mfinale.push_back(it.second);

    }

    g<<cost<<"\n";
    g<<N-1<<"\n";
    for (int i = 0; i < (int)mfinale.size(); i++)
        g<<mfinale[i].first<<" "<<mfinale[i].second<<"\n";

    return 0;
}