#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 200001
#define infinit (1 << 30)

using namespace std;

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

int n, m;
int d[nmax];
bool viz[nmax];
int parent[nmax];

vector < pair <int, int > > muchii[nmax];

struct compara
{
    bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};

priority_queue <int, vector<int>,compara> coada;

void apm(int NodStart)
{
    d[NodStart] = 0;
    coada.push(NodStart);
    for (int i = 2; i <= n ; i++)
        {
            d[i] = infinit;
            coada.push(i);
        }
    parent[NodStart] = -1;
    while (!coada.empty())
    {
        int CurrentNode = coada.top();
        viz[CurrentNode] = true;
        coada.pop();
        for (unsigned int i = 0; i < muchii[CurrentNode].size(); i++)
        {
            int neighbour = muchii[CurrentNode][i].first;
            int cost = muchii[CurrentNode][i].second;
            if (!viz[neighbour] && cost < d[neighbour])
            {
                d[neighbour] = cost;
                parent[neighbour] = CurrentNode;
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m ; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        muchii[x].push_back(make_pair(y,c));
        muchii[y].push_back(make_pair(x,c));
    }
    apm(1);
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += d[i];
    fout << sum << "\n" << n-1 << "\n";
    for (int i = 2;i <= n; i++)
    {
        fout << parent[i] << " " << i << "\n";
    }
    return 0;
}