Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_3e2_pigus_skrydziai_vyr.in

Rezultatų failas: lmio_2018_3e2_pigus_skrydziai_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Pigūs skrydžiai

Justas sukonstravo keleivinį lėktuvą ir įkurė pigių skrydžių bendrovę „Bitlandair“, kuri vykdys skrydžius tarp N Bitlandijos miestų.

Atėjo metas nuspręsti, kokiomis kryptimis bendrovė vykdys skrydžius. Justas užrašė M miestų porų, tarp kurių „Bitlandair“ galėtų vykdyti skrydžius, ir kiekvienai porai nustatė, kiek pelno bendrovei atneštų tokia skrydžių kryptis

Užduotis

Jūsų užduotis – iš Justo sąrašo atrinkti miestų poras, tarp kurių vykdydama skrydžius bendrovė gautų maksimalų pelną. Kadangi „Bitlandair“ turi tik vieną lėktuvą, bet kurios dvi atrinktos poros privalo turėti sutampantį miestą.

Pradiniai duomenys

Pirmoje eilutėje pateikiamas Bitlandijos miestų skaičius N ir Justo užrašytų miestų porų skaičius M.

Tolesnėse M eilučių pateikiama po tris skaičius, aprašančius i-tąją porą – a_i, b_i, p_i. a_i ir b_i yra miestų numeriai, o p_i – pelningumas. Galios sąlyga a_i\\neqb_i ir visos miestų poros bus skirtingos.

Rezultatai

Išveskite vienintelį sveikąjį skaičių – maksimalų „Bitlandair“ pelną.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
5 4
1 2 1
1 3 2
1 4 1
2 4 1
 
4
 
Atrinkus poras 1–2, 1–3, 1–4 pelnas būtų 4 ir tai yra teisingas atsakymas. Atrinkti maršrutus 1–2, 1–4, 2–4 irgi galima, bet pelnas būtų mažesnis – 3.
 
7 9
1 2 2
2 3 5
2 4 3
2 5 5
2 6 4
4 5 8
4 7 6
5 6 2
5 7 6
 
21
 
7 8
1 2 10
1 4 3
2 3 20
2 4 8
3 4 12
4 5 1
4 6 2
4 7 3
 
40

Ribojimai

1\\leqN\\leq300000

1\\leqM\\leq500000

1\\leqa_i,b_i\\leqN

1\\leqp_i\\leq1000000000