Nosaukums
Tālais ceļojums (talcel)
Laika limits
1.00s
Atmiņas limits
32.0 MB
Grūtība
21%

Definīcija

Gudrinieku valstī ir N dažādas pilsētas, numurētas ar skaitļiem no 1 līdz N. Dažus pilsētu pārus savieno divvirzienu ceļi, kuram katram ir savs laiks, kādā to var nostaigāt.

Skots ir tūrists un vēlas apceļot visas pilsētas. Viņam ir savs saraksts, kurā viņš grib apceļot un apskatīt pilsētas (visu N pilsētu konkrēta secība). Ja Skots apskatīja vienu pilsētu un grib nokļūt nākamajā pilsētā sarakstā, tad viņš izvēlas ātrāko maršrutu, lai tur nokļūtu. Skotam nav jāatgriežas sākumā. Ceļojot starp divām pilsētām savā sarakstā, viņš var apmeklēt arī citas pilsētas.

Kaut gan starp katrām divām secīgām pilsētām Skots grib nokļūt pēc iespējas ātrāk, kopumā viņš grib pavadīt savā ceļojumā pēc iespējas vairāk laika. Izrēķiniet, kāds ir ilgākais iespējamais Skota ceļojums!


Ievaddatu raksturojums

Pirmajā rindā dots divi naturāli skaitļi N un M, pilsētu skaits (2 ≤ N ≤ 15) un ceļu skaits (N−1 ≤ MN(N−1)/2).

Katrā no nākamajām M rindām ir doti trīs skaitļi a, b, c, pilsētas, ko savieno viens ceļš, un tā laiks (1 ≤ a, b ≤ N, 1 ≤ c ≤ 106).

Garantēts, ka no katras virsotnes var nokļūt uz katru citu. Starp katrām divām virsotnēm ir ne vairāk kā viens ceļš.


Izvaddatu raksturojums

Izvadiet vienu skaitli, ilgumu garākajam iespējamam Skota ceļojumam.


Piezīmes

Apakšuzdevuma apraksts Punktu skaits
N ≤ 10 20
Bez papildus ierobežojumiem 80
Kopā:     100

Paraugdati

Stdin
4 3
1 2 3
2 3 4
3 4 5
Stdout
28

Stdin
5 6
5 4 50
5 1 46
3 5 70
3 1 60
2 3 53
4 1 37
Stdout
430

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.