#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 200001;
const int EMAX = 400001;

struct edge
{
    int src, dest, weight;
};

int n, m; // the number of nodes and edges
edge A[EMAX]; // stores the tree
int F[NMAX]; // root of node
int H[NMAX]; // weight of tree of element i
edge V[NMAX]; // stores the solution tree
int sum; // sum of the weights

void read()
{
    int i;
    fin >> n >> m;
    for (i = 1; i <= m; ++ i)
        fin >> A[i].src >> A[i].dest >> A[i].weight;
}

inline bool comp(edge E1, edge E2)
{
    if (E1.weight < E2.weight)
        return true;
    return false;
}

int find(int x)
{
    // finds the root for the node x
    while (F[x])
        x = F[x];
    return x;
}

void _union(int x, int y)
{
    if (H[x] > H[y])
        F[y] = x;
    else
        {
         F[x] = y;
         if (H[x] == H[y])
            ++ H[y];
        }
}

void kruskal()
{
    // determines the minimum spanning tree (MST)
    int i, edges, x, y;
    // initialization
    for (i = 1; i <= n; ++ i)
        H[i] = 1;
    edges = 0; // hte number of edges in the beginning is 0
    i = 1;
    while (edges < n - 1)
        {
         x = find(A[i].src);
         y = find(A[i].dest);
         if (x != y)
            {
             V[++ edges] = A[i];
             sum += A[i].weight;
             _union(x, y);
            }
         ++ i;
        }
}

void print()
{
    int i;
    fout << sum << "\n";
    fout << n - 1 << "\n";
    for (i = 1; i < n; ++ i)
        fout << V[i].src << " " << V[i].dest << "\n";
}

int main()
{
    read();
    fin.close();
    sort (A + 1, A + m + 1, comp);
    kruskal();
    print();
    fout.close();
    return 0;
}