#include <fstream>
#include <vector>
#define maxM 524288
#define maxN 200010
using namespace std;

int heap[maxM], heap_size;
int N, M, edge_count;
int v1[400001], v2[400001], cost[400001];
vector<int> G[maxN];
bool seen[maxN], in_heap[400001];

void citire()
{
    ifstream in("apm.in");
    in>>N>>M;
    for (int i=0; i<M; ++i)
    {
        int a, b, c;
        in>>a>>b>>c;
        v1[edge_count] = a;
        v2[edge_count] = b;
        cost[edge_count] = c;
        G[a].push_back(edge_count);
        G[b].push_back(edge_count);
        ++edge_count;
    }
    in.close();
}

inline void swap(int &a, int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}
inline int father(const int &node)
{
    return (node>>1);
}
inline int leftSon(const int &node)
{
    return (node<<1);
}
inline int rightSon(const int &node)
{
    return 1 + (node<<1);
}

void sift(int node)
{
    while (node < heap_size)
    {
        int son = node;
        int left_son = leftSon(node), right_son = rightSon(node);
        if (left_son <= heap_size)
            son = left_son;
        if (right_son <= heap_size && cost[heap[right_son]] < cost[heap[left_son]])
            son = right_son;

        if (cost[heap[son]] < cost[heap[node]])
        {
            swap(heap[son], heap[node]);
            node = son;
        }
        else node = heap_size;
    }
}

void percolate(int node)
{
    while (node > 1)
    {
        int _father = father(node);
        if (cost[heap[node]] < cost[heap[_father]])
        {
            swap(heap[node], heap[_father]);
            node = _father;
        }
        else node = 1;
    }
}

void insert(const int &node)
{
    heap[++heap_size] = node;
    percolate(heap_size);
}

void removeTop()
{
    heap[1] = heap[heap_size--];
    sift(1);
}

int total_cost;
vector<int> apm;

void Prim()
{
    int i, size = G[1].size();
    for (i=0; i<size; ++i)
        insert(G[1][i]);
    seen[1] = 1;
    int seen_nodes = 1;

    while (seen_nodes < N)
    {
        int edge = heap[1];
        removeTop();
        int node = v1[edge];
        if (seen[node] == 1) node = v2[edge];
        if (seen[node] == 0)
        {
            total_cost += cost[edge];
            apm.push_back(v1[edge]); apm.push_back(v2[edge]);

            seen[node] = 1; ++seen_nodes;
            size = G[node].size();
            for (i=0; i<size; ++i)
            {
                edge = G[node][i];
                if (seen[v1[edge]]==0 || seen[v2[edge]]==0)
                    insert(edge);
            }
        }
    }
}

void afisare()
{
    ofstream out("apm.out");
    int i, size = apm.size();
    out<<total_cost<<"\n"<<(size>>1)<<"\n";
    for (i=0; i<size; i+=2)
        out<<apm[i]<<" "<<apm[i+1]<<"\n";
    out.close();
}

int main()
{
    citire();
    Prim();
    afisare();
    return 0;
}