#include <vector>
#include<iostream>
#include<queue>

using namespace std;
/* Чтобы можно было глобально определить массивы, в качестве размера нужно указывать
 * константное целое число, поэтому определим N как максимально возможное число вершин */
const int N = 100000;

int n, m; //количество вершин и ребер в графе

/* храним список смежности в виде массива векторов пар, то есть g[i] - это
 * вектор пар вида (вершина, смежная с i; вес ребра) */
vector<pair<int, int>> g[N];
bool used[N];        // used[i] - была ли использована в остовном дереве вершина i
int cur_mst = 0;     // текущая сумма весов на ребрах остовного дерева
// вектор для хранения ответа - пары (ребро(пара); вес)
vector<pair<pair<int, int>, int>> ans;

void prim() {
    /* Приоритетная очередь - это структура данных, в которой элементы отсортированы по какому-либо
     * приоритету.
     * В качестве параметров указываем тип элементов, которые будут храниться в очереди (пара целых чисел,
     * отображает ребро), тип контейнера для хранения элементов (вектор пар вида (вес, ребро(пара)), компаратор (функция для
     * сравнения элементов, в данном случае более приоритетные - меньшие элементы) */
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
    // начинаем построение минимального остовного с вершины 0 (абстрактное ребро 0, 0)
    // то есть как будто пришли в вершину 0 из самой себя по ребру с весом 0
    q.push(make_pair(0, make_pair(0, 0)));

    while (!q.empty()) { // пока очередь не станет пустой
        pair<int, pair<int, int>> c = q.top(); // достаем верхний элемент из очереди (то есть, с самым меньшим весом)
        q.pop(); // удаляем его из очереди

        int w = c.first;         // вес текущего ребра
        int v = c.second.first;  // вершина, в которую это ребро переходит
        int p = c.second.second; // откуда идет ребро

        if (used[v]) continue; // если вершина v уже есть в остовном дереве, то это ребро не подходит

        used[v] = true; // помечаем вершину v как использованную
        cur_mst += w;   // добавляем вес текущего ребра
        if (p != v) // если это не абстрактное ребро из самого начала
        // добавляем ребро в ответ, добавляем 1 к вершинам для перехода в 1-индексацию
        ans.push_back(make_pair(make_pair(p + 1, v + 1), w));

        // проходим по всем смежным вершинам вершины v
        for (pair<int, int> e : g[v]) {
            int u = e.first;        // смежная вершина
            int weight = e.second;  // вес ребра до нее

            if (!used[u]) {               // если вершины u еще нет в остовном дереве, добавим ее в очередь
                q.push(make_pair( weight, make_pair(u, v)));    // добавляем пару (вес; вершина). сначала идет вес, потому что сортируем по весу
            }
        }
    }
}

int main() {
    setlocale(LC_ALL, "rus");
    cin >> n >> m;
    // считываем все ребра
    for (int i = 0; i < m; ++i) {
        int a, b, w;  // a и b - вершины, w - вес ребра
        cin >> a >> b >> w;
        a--; b--; //переход в 0-индексацию
        // добавляем пары вида (смежная вершина; вес ребра)
        g[a].push_back(make_pair(b, w));
        g[b].push_back(make_pair(a, w));
    }

    prim(); // вызываем функцию поиска минимального остовного дерева по алгоритму Прима

    cout << "Сумма весов ребер минимального остовного дерева: " << cur_mst << endl;
    cout << "Минимальное остовное дерево: " << endl;
    // проходи по всем ребрам в ответе
    for (auto edge : ans) {
        cout << edge.first.first << " " << edge.first.second << " " << edge.second << endl;
    }
}

/*
6 8
1 2 7
2 3 5
1 4 4
4 3 7
2 4 9
4 5 10
3 5 13
5 6 11
*/