D. Графаар аялах

хугацааны хязгаарлалт 0.5 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Чиглэлгүй, жинтэй граф ѳгѳгдѳв. $1$ дугаартай цэгээс эхлэн бусад цэг бүрээр ядаж нэг удаа дайран гарах хамгийн богино циклийн уртыг ол. Графд хоёр цэгийн хооронд олон ирмэгтэй байж болно. Мѳн гогцоотой (өөрөөсөө гараад өрлүүгээ ирдэг зам) байж болно.

Оролт

Эхний мѳрѳнд оройн тоо, ирмэгийн тоог харгалзан илэрхийлэх $n$, $m$ ($1 ≤ n ≤ 15$, $0 ≤ m ≤ 2000$) бүхэл тоонууд ѳгѳгднѳ. Дараагийн $m$ мѳрѳнд $x$, $y$,$w$ ($1 ≤ x, y ≤ n$, $1 ≤ w ≤ 10000$) бүхэл тоон гурвал, энд $x, y$ нь ирмэгийн оройн цэгүүд, $w$ нь ирмэгийн урт болно.

Гаралт

Хамгийн богино циклийн урт, эсвэл тийм цикл олдохгүй бол $-1$ гэж хэвлэ.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
3 3
1 2 1
2 3 1
3 1 1
Гаралт
3
Оролт
3 2
1 2 3
2 3 4
Гаралт
14
Сэтгэгдлүүдийг ачааллаж байна...