#include <fstream>
#include <queue>
#include <bitset>
#include <cstring>

using namespace std;

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

const int nMax = 200000 + 20;

struct Node 
{
    int node, w = 0;
};

struct Comp
{
    bool operator() (Node a, Node b)
    {
        return a.w > b.w;
    }
};

priority_queue<Node, vector<Node>, Comp > q;
vector < Node > g[nMax];
int parent[nMax], cost[nMax];
bitset < nMax > viz;
int n, m;

void Prim()
{
    memset (cost, 5, sizeof(cost));

    q.push({1, 0});
    cost[1] = 0;

    while (!q.empty())
    {
        int node = q.top().node;
        q.pop();

        viz[node] = 1;

        for (Node next : g[node])
        {
            int nextNode = next.node;
            int w = next.w;

            if (!viz[nextNode] && cost[nextNode] > w)
            {
                parent[nextNode] = node;
                cost[nextNode] = w;
                q.push({nextNode, w});
            }
        }

    }
}

int main()
{   
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int node, next, w;

        fin >> node >> next >> w;

        g[node].push_back({next, w});
        g[next].push_back({node, w});
    }

    Prim();

    int sum = 0;

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

    fout << sum << '\n' << n - 1 << '\n';

    for (int i = 1; i <= n; i++)
    {
        if (parent[i] != 0)
        {
            fout << i << ' ' << parent[i] << '\n';
        }
    }


    fin.close();
    fout.close();
    return 0;
}