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!

Pirmajā rindā dots divi naturāli skaitļi N un M, pilsētu skaits (2 ≤ N ≤ 15) un ceļu skaits (N−1 ≤ M ≤ N(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 ≤ 10⁶).

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ļš.

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