Ђоле Програмер, бивши такмичарски програмер, а сада градоначелник Бајтграда, престонице Бајтовије, треба да смисли план за нови градски метро. Већ је одређено да ће постојати \(N\) станица, као и где ће се налазити.

Постоји \(M\) различитих предлога за метро линије, од којих Ђоле мора да изабере подскуп. Сваки предлог се састоји од две станице које линија директно повезује, као и цену изградње линије. Све цене изградње метро линија су међусобно различите. Познато је да је за сваки добар метро потребно да будe задовољен следећи услов: - може се стићи од било које станице до било које друге, на тачно један начин.

Такође, Ђоле жели да укупна цена метроа (збир цена изабраних метро линија) буде што мања.

Када је овако формално дефинисао проблем, Ђоле се одмах сетио сличних задатака из својих такмичарских дана, али није могао да се сети тачно алгоритма који треба да користи. Сетио се да алгоритам гласи овако: - поређамо све планове за метро линије у низ, неким редоследом; - пролазимо кроз линије једну по једну тим редоследом и обавезно прихватамо план за ту метро линију уколико није у конфликту са до сада прихваћеним линијама; - кажемо да је линија у конфликту са до сада прихваћеним линијама уколико, када додамо ту линију међу прихваћене линије, постоји више од једног начина да се стигне између неке две станице.

Ђоле није успео да се сети тачно који редослед линија (поредак) треба да користи, али знамо да воли велике бројеве и волео би да буду што ближе почетку поретка. Иако је ипак најбитнија цена, ви желите и да Ђоле буде срећан. Зато, ваш задатак је да нађете лексикографски највећи поредак линија по цени који ће, пратећи горенаведени алгоритам, још увек да нађе најјефтинији могућ метро.

Опис функцијe

Потребно је да имплементирате функцију

• \(NadjiPoredak(N, M, X[\ldots], Y[\ldots], W[\ldots])\)

где је \(N\) број станица у Бајтграда, а \(M\) број предлога линија. Низови \(X\), \(Y\) и \(W\) описују предлоге линија, где су \(X\) и \(Y\) индекси станица које повезује, а \(W\) цена да се линија направи. Потребно је да функција врати тражени поредак. Враћени низ треба да садржи цене линија, поређане у одговарајући редослед. Низови \(X\), \(Y\) и \(W\) су индексирани од \(1\), поредак је индексиран од \(0\).

Примери

Нека су \(N=4\) и \(M = 5\), и нека су низови \(X=\{1, 2, 2, 3, 1\}\), \(Y=\{ 2, 3, 4, 4, 4\}\) и \(W=\{50, 10, 20, 30, 40\}\). Лексикографски највећи поредак који даје најјефтинији метро план је \(\{40, 20, 50, 10, 30\}\). Овим поретком добијамо најјефтинији метро план који садржи гране \(2\), \(3\) и \(5\), укупне цене \(70\).

Нека су \(N=5\) и \(M = 5\), и нека су низови \(X=\{2, 2, 1, 1, 3\}\), \(Y=\{ 5, 4, 2, 4, 4\}\) и \(W=\{12, 3, 50, 11, 36\}\). Лексикографски највећи поредак који даје најјефтинији метро план је \(\{36, 12, 11, 3, 50\}\). Овим поретком добијамо најјефтинији метро план који садржи гране \(1\), \(2\), \(4\) и \(5\), укупне цене \(62\).

Ограничења

• \(1 \leq N, M \leq 3\cdot10^5\).
• \(1 \leq X_i, Y_i \leq N\).
• \(1 \leq W_i \leq 10^9\).
• Гарантује се да ће бити могуће направити макар један метро план.
• \(W_i \neq W_j\), за \(i \neq j\).
• \(X_i \neq Y_i\), за \(1 \leq i \leq M\).
• Дозвољено је да више планова предлаже линију између неке две станице (али са различитом ценом).

Подзадаци

Тест примери су подељени у \(6\) подзадатка: - [7 поена]: \(M \leq 9\). - [11 поена]: Сваки план метро линије припада највише једном циклусу (погледати напомену) - [9 поена]: \(N, M \leq 5000\) и постоји најјефтинији метро план тако да из сваке станице постоји највише две метро линије. - [12 поена]: Постоји најјефтинији метро план тако да из сваке станице постоји највише две метро линије. - [20 поена]: \(N, M \leq 5000\). - [41 поена]: Нема додатних ограничења.

Детаљи имплементације

Потребно је да пошаљете тачно један фајл tsm.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

vector<int> NadjiPoredak(int N, int M, int* X, int* Y, int* W);

Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова.

Уз задатак, обезбеђен вам је “template” фајл code.cpp које можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N\) и \(M\).
• У наредних \(M\) редова по три броја у сваком реду, \(X_i\) \(Y_i\) \(W_i\).

Затим овај програм позива вашу функцију и штампа поредак који је вратила ваша функција.

Напомена

Кажемо да је поредак грана \(a\) лексикографски већи од поретка \(b\) ако важи да је тежина гране \(a_i\) већа од тежине гране \(b_i\), за најмање \(i\) за које те тежине нису једнаке.

Циклус је низ станица \(x_1 x_2 \ldots x_k\) за неко \(k\), где важи да \(x_1 = x_k\), ниједна друга станица се не појављује више од једанпут и постоји план метро линија који директно повезује станице \(x_i\) и \(x_{i+1}\) за свако \(1 \leq i < k\). Кажемо да ти планови метро линија припадају том циклусу.