#include <bits/stdc++.h>
using namespace std;
const int NMAX = 200010;

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

struct NodCost
{
    int nod, cost;
    bool operator<(const NodCost &other) const
    {
        return cost < other.cost;
    }
};

NodCost dist[NMAX];
vector<NodCost> G[NMAX];
priority_queue<NodCost> Q;
vector<NodCost> adj[NMAX];
vector<pair<int, int>> edges;
bool in_apm[NMAX];
int n, m;
int cost;

void prim()
{
    for (int i = 1; i <= n; i++)
    {
        dist[i] = {-1, INT_MAX};
    }
    in_apm[1] = true;
    dist[1] = {0, 0};
    for (auto u : adj[1])
    {
        dist[u.nod] = {1, u.cost};
        Q.push(u);
    }
    while (!Q.empty())
    {
        auto v = Q.top();
        Q.pop();
        if (in_apm[v.nod])
        {
            continue;
        }
        in_apm[v.nod] = 1;
        cost += v.cost;
        if (v.nod != 1)
        {
            edges.push_back({v.nod, dist[v.nod].nod});
        }
        for (auto u : adj[v.nod])
        {
            if (u.cost < dist[u.nod].cost)
            {
                dist[u.nod] = {u.cost, v.nod};
                Q.push(u);
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    prim();
    fout << cost << '\n';
    fout << n - 1 << '\n';
    for (auto edge : edges)
    {
        fout << edge.first << ' ' << edge.second << '\n';
    }
    return 0;
}