#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

int n, m, cost;
int arbore[200005];
bool used[200005];
const int inf = 9999999999;
vector < pair < int, int > > graph[200005];

void Prim (int start)
{
    int found, minim, parent;
    used[start] = 1;

    for (int k=1; k<=n-1; k++)
    {
        minim = inf;

        for (int i=1; i<=n; i++)
        {
            if (used[i])
            {
                int lg = graph[i].size() - 1;

                for (int j=0; j<=lg; j++)
                {
                    if (graph[i][j].second < minim && !used[graph[i][j].first])
                    {
                        minim = graph[i][j].second;
                        found = graph[i][j].first;
                        parent = i;
                    }
                }
            }
        }

        used[found] = 1, cost += minim;
        arbore[found] = parent;
    }
}

void PrintArbore ()
{
    g << cost << "\n";
    g << n-1 << "\n";
    memset(used, 0, sizeof(used));

    for (int i=n; i>=1; i--)
    {
        if (!used[i] && !used[arbore[i]] && arbore[i] != 0)
        {
            g << arbore[i] << " " << i << "\n";
        }
    }
}

int main()
{
    f >> n >> m;
    while (m --)
    {
        int x, y, val;
        f >> x >> y >> val;
        graph[x].push_back(make_pair(y, val));
        graph[y].push_back(make_pair(x, val));
    }

    Prim(1);
    PrintArbore();

    return 0;
}