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

using namespace std;

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

const int nMax = 200000 + 10;
const int inf = (1 << 30);


int n, m;

struct Node
{
    int to, w;
};

int cost[nMax], p[nMax];

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

vector < Node > l[nMax];

bitset < nMax > viz;

priority_queue < Node, vector < Node >, comp > q;

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

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

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

        q.pop();

        viz[node] = 1;

        for (Node next : l[node])
        {
            if (!viz[next.to] && cost[next.to] > next.w)
            {
                cost[next.to] = next.w;
                p[next.to] = node;
                q.push(next);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
 
    for (int i = 1; i <= m; i++)
    {
        int node, next, w;
 
        fin >> node >> next >> w;
 
        l[node].push_back({next, w});
        l[next].push_back({node, w});
    }
 
    Prim(1);
 
    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 (p[i] != 0)
        {
            fout << i << ' ' << p[i] << '\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}