C. Гар бөмбөг

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

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

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

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

Петяа гар бөмбөгт маш дуртай. Нэг өдөр тэрээр гар бөмбөгийн тэмцээнд хоцорч байлаа. Түүнд өөрийн гэсэн машин байсангүй тул такси барихаар шийдсэн. Хот нь зарим нь хоёр чиглэлтэй замаар холбогдсон $n$ уулзвараас бүрдэнэ. Зам бүрийн урт нь эерэг бүхэл тоон метрээр хэмжигдэх ба замууд өөр өөр урттай байж болно.

Эхлээд уулзвар бүр дээр нэг такси зогссон байна. Хэрэв хоорондын зай нь $t_i$-аас ба бол $i$ дахь уулзвар дээр байгаа таксиний жолооч Петяаг өөр нэг уулзварт (магадгүй хэд хэдэн уулзварын даван) хүргэж өгч чадна. Мөн унааны хөлс нь зайнаас хамаардаггүй ба $c_i$ төгрөг байна. Такси замын голд зогсож чадахгүй. Танкси болгон ганц л удаа хэрэглэгдэнэ. Петяа эхлээд зогсож байсан газраасаа л такси бариж чадна.

Одоо Петяа $x$ уулзвар дээр байгаа бөгөөд гар бөмбөгийн тэмцээн $y$ уулзвар дээр болж байгаа. Гар бөмбөгийн тэмцээний газар очихын тулд үрэх хамгийн бага мөнгөний хэмжээг ол.

Оролт

Эхний мөр $n, m (1 <= n <= 1000, 0 <= m <= 1000)$ бүхэл тоонуудыг агуулна. Тэдгээр н уулзвар болон замын тоонууд. Уулзварууд 1-ээс $n$ хүртэл дугаарлагдсан. Дараагийн мөр $x, y$ бүхэл тоонуудыг агуулна. Тэдгээр нь эхний болон төгсгөлийн уулзварууд. Дараагийн $m$ мөр замуудыг дүрслэнэ. Зам бүр гурван бүхэл тоо $u_i, v_i, w_i (1 <= u_i, v_i <= n, 1 <= w_i <= 10^9)$-аар дүрслэгдэх ба тэдгээр нь тухайн замаар холбогдсон уулзварууд болон замын урт юм. Дараагийн $n$ мөр $i$ дахь зогсоол дээр зогсож байгаа таксины жолоочийн явж чадах хамгийн их зай, унааны үнийг дүрсэлсэн $n$ ширхэг $t_i, c_i (1 <= t_i, c_i <= 10^9)$ хос тоонуудыг агуулна. Зам заавал өөр өөр уулзваруудыг холбох ба харин хоёр уулзварын дунд нэгээс олон зам байж болно. Мөрөнд байгаа тоо бүр зөвхөн нэг хоосн зайгаар тусгаарлагдана.

Гаралт

Хэрэв таксинууд Петяаг зорьсон газар нь хүргэж чадахгүй бол "-1"-ийг хэвлэ (апострофгүйгээр). Эсрэг тохиолдолд хамгийн бага үнийг хэвлэнэ.

C++ дээр 64-bit бүхэл тоог уншихдаа бүү %lld хэрэглэ. cin, cout урсгал эсвэл %I64d хэрэглэ.

Орчуулсан: devman

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

Оролт
4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7
Гаралт
9

Тэмдэглэл

Тохиромжтой зам нь 1-ээс 2-т (4-р уулзвараар) хүрч дараа нь 2-оос 3-т очно. Нийт 7+2=9 төгрөг болно.

Сэтгэгдлүүдийг ачааллаж байна...