E. Путешествие
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы находитесь в неориентированном связном графе с $$$n$$$ вершинами и $$$m$$$ взвешенными рёбрами. Рёбра пронумерованы от $$$1$$$ до $$$m$$$. $$$i$$$-е ребро соединяет вершины $$$u_i$$$ и $$$v_i$$$ и имеет вес $$$w_i$$$. Вы решили совершить замечательное путешествие по графу.

Предположим, вы находитесь в вершине $$$x$$$. Вы можете выполнять следующие операции любое количество раз:

  1. Отметить ребро, соединяющее $$$x$$$ и $$$y$$$, сделать фотографии вдоль ребра и переместиться в $$$y$$$, что стоит ровно вес ребра.
  2. Переместиться в другую произвольную вершину $$$z \neq x$$$ на поезде. Вы можете выбрать любой путь $$$x\leadsto z$$$ (не обязательно простой), и стоимость будет весом ребра с максимальным индексом на этом пути. Формально, предположим, вы выбрали путь с индексами рёбер $$$e_1, e_2, \ldots, e_k$$$, такой что существует последовательность вершин $$$p_1, p_2, \ldots, p_{k+1}$$$ такая что $$$x = p_1$$$, $$$z = p_{k+1}$$$ и для всех $$$i$$$ в $$$[1, k]$$$ ребро $$$e_i$$$ соединяет $$$p_{i}$$$ и $$$p_{i+1}$$$,стоимость равна $$$w_{\max_{i=1}^k e_i}$$$.

Вы сейчас находитесь в вершине $$$1$$$, и вам нужно отметить каждое ребро хотя бы один раз и вернуться в вершину $$$1$$$. Рассчитайте минимальную стоимость.

Обратите внимание, что стоимость перемещения не является максимальным весом на пути и не самим максимальным индексом. Если у вас есть вопросы, обратитесь к разделу Примечания ниже.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$T$$$ ($$$1 \le T \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$0 \le m \le 10^6$$$).

Затем $$$m$$$ строк, $$$i$$$-я строка содержит три целых числа $$$u_i, v_i, w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w \le 10^9$$$) — это означает, что ребро с индексом $$$i$$$ соединяет вершины $$$u_i$$$ и $$$v_i$$$ с весом $$$w_i$$$.

Гарантируется, что описанный граф связен.

Также обратите внимание, что граф может иметь петли и мультирёбра.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем набора входных данных каждая не превышают $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальная стоимость.

Пример
Входные данные
5
5 6
2 4 15
2 5 4
1 3 6
2 3 9
1 2 10
3 4 7
4 3
1 2 3
1 3 2
1 4 1
2 3
1 2 1
2 1 3
1 1 4
6 6
2 3 10
1 3 10
5 6 10
6 6 1
4 5 10
3 4 10
5 5
1 2 4
5 1 5
4 3 6
2 4 10
1 4 7
Выходные данные
58
8
8
71
43
Примечание

Ccылка на визуализатор.

Пусть $$$u \xrightarrow{e} v$$$ обозначает переход к вершине $$$v$$$ из вершины $$$u$$$ по ребру $$$e$$$.

В первом наборе входных данных одно из возможных решений:

  1. Изначально вы находитесь в вершине $$$1$$$.
  2. Отметьте ребро $$$3$$$ и переместитесь в вершину $$$3$$$, стоимость $$$6$$$.
  3. Отметьте ребро $$$6$$$ и переместитесь в вершину $$$4$$$, стоимость $$$7$$$.
  4. Отметьте ребро $$$1$$$ и переместитесь в вершину $$$2$$$, стоимость $$$15$$$.
  5. Отметьте ребро $$$4$$$ и переместитесь в вершину $$$3$$$, стоимость $$$9$$$.
  6. Переместитесь в вершину $$$5$$$. Выбрав путь $$$3 \xrightarrow{6} 4 \xrightarrow{1} 2 \xrightarrow{2} 5$$$, мы можем достичь стоимости $$$7$$$, так как максимальный индекс среди рёбер на пути равен $$$6$$$, и $$$w_6 = 7$$$. Обратите внимание, что нас не интересует максимальный вес на пути при использовании операции 2.
  7. Отметьте ребро $$$2$$$ и переместитесь в вершину $$$2$$$, стоимость $$$4$$$.
  8. Отметьте ребро $$$5$$$ и переместитесь в вершину $$$1$$$, стоимость $$$10$$$.

Общая стоимость составляет $$$6+7+15+9+7+4+10=58$$$.

Во втором наборе одно из возможных решений:

  1. Отметьте ребро $$$1$$$ и переместитесь в вершину $$$2$$$, стоимость $$$3$$$.
  2. Переместитесь в вершину $$$3$$$ по пути $$$2 \xrightarrow{1} 1 \xrightarrow{3} 4 \xrightarrow{3} 1 \xrightarrow{2} 3$$$, стоимость $$$1$$$. Обратите внимание, что выбранный путь в операции 2 может не быть простым.
  3. Отметьте ребро $$$2$$$ и переместитесь в вершину $$$1$$$, стоимость $$$2$$$.
  4. Отметьте ребро $$$3$$$ и переместитесь в вершину $$$4$$$, стоимость $$$1$$$.
  5. Переместитесь в вершину $$$1$$$ по пути $$$4 \xrightarrow{3} 1$$$, стоимость $$$1$$$.