Masala #WRPWDOOXTL

Sizga nnn ta tugun va kkk ta qirra berilgan. Har bir qirra quyidagi ko‘rinishda: u v w — bu u tuguni bilan v tuguni orasidagi qirra va uning narxi (xarajati) www. Graf yo‘nalishsiz (undirected). Berilgan boshlang‘ich tugun a va maqsad tugun b uchun a dan b ga borish uchun zarur bo‘lgan minimal jami pulni (eng kam xarajat) va shu xarajatga olib keluvchi yo‘lni toping. Agar yo‘l mavjud bo‘lmasa -1 chiqaring.

Birinchi qatorda ikkita butun son: n k — tugunlar soni va qirralar soni.

Keyingi k qatorning har birida uchta son: u v w (0 ≤ u,v ≤ n-1) — tugunlar va yo‘l narxi.

Oxirgi qatorda ikkita son: a b — boshlang‘ich va maqsad tugunlari.
 

• 2≤n≤2*1e5
• 1≤k≤2⋅1e5
• 0≤u,v≤n−1
• 1≤w≤1e9
• 0≤a,b≤n−1

• Agar a dan b ga yo‘l mavjud bo‘lsa:
  • Birinchi qatorda minimal jami narx.
  • Ikkinchi qatorda shu narxga ega yo‘lning tugunlari ketma-ketligi.
• Agar yo‘l mavjud bo‘lmasa:
  • Faqat -1