Masala #AIGYGAB2RC

Sizga N ta shahar va ular orasidagi M ta bir tomonlama yo‘llar berilgan. Har bir yo‘l u → v narxi C — musbat butun son.

Sizning vazifangiz — avval 1-shahardan N-shaharga eng arzon yo‘l bilan borish, so‘ng N-shahardan 1-shaharga eng arzon yo‘l bilan qaytish. Bu ikkita yo‘l mustaqil (ya’ni, borish va qaytish yo‘llari bir-biriga bog‘liq bo‘lishi shart emas). Topilgan eng arzon borish yo‘lining narxi D[borish] borish​, eng arzon qaytish yo‘lining narxi D[qaytish] qaytish​ bo‘lsa, umumiy narx

D[umumiy] = D[borish] + D[qaytish]

bo‘ladi. Agar 1-dan N-ga borish yoki N-dan 1-ga qaytish mumkin bo‘lmasa, bunday sayohat amalga oshmaydi va javob −1 bo‘ladi.

Muhim: Yo‘llar bir tomonlama bo‘lgani uchun u → v yo‘li mavjudligining v → u yo‘li mavjudligini anglatmasligini yodda tuting.

Birinchi qatorda ikkita butun son: N va M — shaharlar soni va yo‘llar soni:

 1 ≤ N, M ≤ 10^5

Keyingi M qatorning har birida uchta butun son: bu u shahridan v shahriga yo‘l borligini va uning narxi C ekanligini bildiradi. 

1 ≤ u, v ≤ N, u ≠ v

1 ≤ C ≤ 10^9

Bitta butun son — agar 1-dan N-ga borish va N-dan 1-ga qaytish ikkalasi ham mumkin bo‘lsa, minimal umumiy narx D[umumiy​] ni chiqaring. Aks holda -1 ni chiqaring.