#include <fstream>
#include <vector>

using namespace std;

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

const int INF = 2e9;

class minHeap
{
    private:
        struct heapElement
        {
            int key;
            int value;

            heapElement();
            heapElement(const int _KEY, const int _VALUE);
        };

        int capacity;
        int heapSize;

        int* pos;
        heapElement* harr;

    public:
        minHeap();
        minHeap(const int _CAPACITY, const int _MAXKEY);
        ~minHeap();

        int parent(const int node) {return node / 2;}
        int leftChild(const int node) {return node * 2;}
        int rightChild(const int node) {return node * 2 + 1;}

        void heapifyUp(int node);
        void heapifyDown(int node);

        void insertElement(const int key, const int value);
        void changeValue(const int key, const int newValue);

        pair < int, int > getMin();
        void extractMin();
};

minHeap :: heapElement :: heapElement()
{
    key = 0;
    value = 0;
}

minHeap :: heapElement :: heapElement(const int _KEY, const int _VALUE)
{
    key = _KEY;
    value = _VALUE;
}

minHeap :: minHeap()
{
    capacity = 0;
    heapSize = 0;
    pos = NULL;
    harr = NULL;
}

minHeap :: minHeap(const int _CAPACITY, const int _MAXKEY)
{
    capacity = _CAPACITY;
    heapSize = 0;
    pos = new int[_MAXKEY + 1];
    harr = new heapElement[_CAPACITY + 1];
}

minHeap :: ~minHeap()
{
    delete[] pos;
    delete[] harr;
}

void minHeap :: heapifyUp(int node)
{
    while (node > 1 && harr[node].value < harr[parent(node)].value)
    {
        swap(pos[harr[node].key], pos[harr[parent(node)].key]);
        swap(harr[node], harr[parent(node)]);
        node = parent(node);
    }
}

void minHeap :: heapifyDown(int node)
{
    int child = 0;

    do
    {
        child = 0;

        if (leftChild(node) <= heapSize)
        {
            child = leftChild(node);

            if (rightChild(node) <= heapSize && harr[rightChild(node)].value < harr[leftChild(node)].value)
                child = rightChild(node);

            if (harr[child].value >= harr[node].value)
                child = 0;
        }

        if (child)
        {
            swap(pos[harr[node].key], pos[harr[child].key]);
            swap(harr[node], harr[child]);
            node = child;
        }

    }while (child);
}

void minHeap :: insertElement(const int key, const int value)
{
    if (heapSize == capacity)
        return;

    heapSize++;
    harr[heapSize] = heapElement(key, value);
    pos[key] = heapSize;

    heapifyUp(heapSize);
}

void minHeap :: changeValue(const int key, const int newValue)
{
    if (!pos[key])
        return;

    harr[pos[key]].value = newValue;

    heapifyUp(pos[key]);
    heapifyDown(pos[key]);
}

pair < int, int > minHeap :: getMin()
{
    if (!heapSize)
        return {-1, 0};

    return make_pair(harr[1].key, harr[1].value);
}

void minHeap :: extractMin()
{
    if (!heapSize)
        return;

    pos[harr[1].key] = 0;
    harr[1] = harr[heapSize];
    pos[harr[1].key] = 1;
    heapSize--;

    heapifyDown(1);
}

struct edge
{
    int node;
    int cost;

    edge()
    {
        node = 0;
        cost = 0;
    }

    edge(const int _NODE, const int _COST)
    {
        node = _NODE;
        cost = _COST;
    }
};

int n, m;

bool used[200001];

int dist[200001];

int parent[200001];

vector < edge > adj[200001];


void read()
{
    f >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, c; f >> x >> y >> c;
        adj[x].push_back(edge(y, c));
        adj[y].push_back(edge(x, c));
    }
}

void prim()
{
    int cost = 0;

    vector < pair < int, int > > edges;

    minHeap h(n, n);

    used[1] = true;

    for (int i = 2; i <= n; i++)
    {
        used[i] = false;
        parent[i] = 0;
        dist[i] = INF;
        h.insertElement(i, INF);
    }

    for (auto it : adj[1])
    {
        h.changeValue(it.node, it.cost);
        dist[it.node] = it.cost;
        parent[it.node] = 1;
    }

    for (int i = 1; i < n; i++)
    {
        int node = h.getMin().first;
        int d = h.getMin().second;
        h.extractMin();

        cost += d;
        edges.push_back(make_pair(node, parent[node]));

        used[node] = true;
        for (auto it : adj[node])
            if (it.cost < dist[it.node])
            {
                dist[it.node] = it.cost;
                h.changeValue(it.node, it.cost);
                parent[it.node] = node;
            }
    }

    g << cost << "\n";
    g << edges.size() << "\n";
    for (auto it : edges)
        g << it.first << " " << it.second << "\n";
}

int main()
{
    read();
    prim();
    return 0;
}