#include <fstream>
#include <vector>

using namespace std;

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

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

        heapElement *harr;
        int *pos;
        int capacity;
        int heapSize;

    public:
        minHeap(int cap, int maxKey);
        ~minHeap();

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

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

        int getMin();
        void extractMin();

        void insertElement(int key, int value);
        void decreaseKey(int key, int newValue);
};

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

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

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);
}

int minHeap :: getMin()
{
    return harr[1].key;
}

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

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

    heapifyDown(1);
}

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

    heapSize++;
    harr[heapSize].key = key;
    harr[heapSize].value = value;
    pos[key] = heapSize;

    heapifyUp(heapSize);
}

void minHeap :: decreaseKey(int key, int newValue)
{
    harr[pos[key]].value = newValue;
    heapifyUp(pos[key]);
}

struct edge
{
    int node;
    int cost;

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

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

const int INF = 2e9;

int n, m;

int cost[200001];
int parent[200001];

bool used[200001];

vector < edge > adj[200001];

void prim(int root, int &totalCost, vector < pair < int, int > > &edges)
{
    totalCost = 0;
    edges.clear();

    for (int i=1; i<=n; i++)
    {
        used[i] = false;
        cost[i] = INF;
    }

    used[root] = true;
    for (auto it : adj[root])
    {
        cost[it.node] = it.cost;
        parent[it.node] = root;
    }

    minHeap h(n, n);
    for (int i=1; i<=n; i++)
        if (i != root)
            h.insertElement(i, cost[i]);

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

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

        for (auto it : adj[node])
            if (!used[it.node] && it.cost < cost[it.node])
            {
                cost[it.node] = it.cost;
                parent[it.node] = node;
                h.decreaseKey(it.node, it.cost);
            }
    }
}

int main()
{
    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));
    }

    int totalCost = 0;
    vector < pair < int, int > > edges;

    prim(1, totalCost, edges);

    g << totalCost << "\n";

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

    return 0;
}