#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 200001;
const int MMAX = 400001;
int n, m, k;
long long c;

struct edge
{
    int x, y, cost;
} v[MMAX], res[NMAX];

vector<pair<int, int>> adj[NMAX];

struct compare_edges
{
    bool operator()(edge a, edge b)
    {
        return a.cost > b.cost;
    }
};
priority_queue<edge, vector<edge>, compare_edges> pq;
bool visited[NMAX];

void Prim()
{
    visited[1] = true;

    for (int i = 0; i < adj[1].size(); i++)
    {
        int neighbor = adj[1][i].first;
        int cost = adj[1][i].second;
        pq.push({ 1, neighbor, cost });
    }

    while (!pq.empty() && k < n - 1)
    {
        edge best_edge = pq.top();
        pq.pop();

        int u = best_edge.x;
        int v = best_edge.y;
        int cost = best_edge.cost;

        if (visited[v])
            continue;

        visited[v] = true;
        c = c + cost;
        res[++k] = best_edge;

        for (int i = 0; i < adj[v].size(); i++)
        {
            int next_neighbor = adj[v][i].first;
            int next_cost = adj[v][i].second;

            if (!visited[next_neighbor])
            {
                pq.push({ v, next_neighbor, next_cost });
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;

    for (int i = 1; i <= m; i++)
    {
        adj[v[i].x].push_back({ v[i].y, v[i].cost });
        adj[v[i].y].push_back({ v[i].x, v[i].cost });
    }

    Prim();

    fout << c << '\n';
    fout << k << '\n';
    for (int i = 1; i <= k; i++)
        fout << res[i].x << " " << res[i].y << '\n';

    return 0;
}