E. Ерөнхийлөгч ба Замууд

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

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

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

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

Berland нь $n$ хоттой бөгөөд нийслэл хот нь $s$, харин уламжлалт Ерөнхийлөгчийн хот нь $t$ ($s ≠ t$) юм. Хотууд нь хоорондоо нэг урсгалтай замаар холбогдсон ба зам бүрээр явж өнгөрөөх хугацаа нь эерэг бүхэл тоо.

Нэгэн жил Ерөнхийлөгч өөрийн уламжлалт хот $t$-д зочилсон, түүний машины цуваа нь $s$-ээс $t$-рүү ямар нэгэн замаар явж очсон (тэрээр өөрөө үргэлж онгоцондоо эргэж ирдэг). Ерөнхийлөгч их зав муутай хүн болохоор үргэлж $s$-ээс $t$-рүү хүрэх хамгийн хурдан явах замыг сонгодог.

Зам тээврийн яам зам бүрийн хувьд дараахи мэдээллийг мэдэхийг хүсчээ: Тухайн зам Ерөнхийлөгчийн аялалын маршрутад орох эсэх, хэрвээ орохгүй тохиолдолд уг замыг зассанаар нийслэл хотоос уламжлалт Ерөнхийлөгчийн хот хүртэлх хамгийн богино маршрутад уг зам хамаарагдах эсэх. Мэдээж засагдахгүй замын аялах хугацаа нь нэгээс бага. Berland-ын бусад яамдууд зам засварын төсвийг хамгийн бага байлгахаар анхаарч байгаа. Мөн энэ нь яг таг нарийн тооцоололд дуртай учраас эерэг бүхэл аялах хугацаатай замуудыг л засдаг.

Оролт

Эхний мөрөнд дөрвөн тоо $n$, $m$, $s$, $t$ ($2 ≤ n ≤ 10^{5}; 1 ≤ m ≤ 10^{5}; 1 ≤ s, t ≤ n$) -- Berland дахь хот болон замуудын тоо ба нийслэл болон Ерөнхийлөгчийн амьдардаг хотын дугаар ($s ≠ t$).

Дараагийн m ширхэг мөрөнд замуудын мэдээлэл байна. Зам болгон нь бүлэглэсэн гурван тоогоор өгөгдсөн $a_{i}, b_{i}, l_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}; 1 ≤ l_{i} ≤ 10^{6}$) -- $i$-р замаар холбогдсон хотууд ба замаар явах хугацаа. Зам нь $a_i$-аас $b_i$-руу чиглэсэн.

Хотууд нь 1-ээс $n$ хүртэл дугаарлагдсан. Аль ч хос хот нь хоорондоо хэд хэдэн замтай байж болно. $s$ хотоос $t$ хотруу хүрэх зам заавал байна.

Гаралт

$m$ мөр хэвлэ. $i$ дахь мөрөнд $i$ дахь замын талаар мэдээлэл байна(замууд нь оролтонд байгаа дарааллаар дугаарлагдсан).

Хэрвээ ерөнхийлөгч аялалынхаа явцад уг замыг заавал дайрч өнгөрөх бол зөвхөн "YES"(хашилтгүйгээр) гэж хэвлэнэ.

Эсрэг тохиолдолд, хэрвээ $i$ дахь зам засагдах боломжтой бөгөөд түүгээр дамжин өнгөрөх хугацаа нь эерэг ба ерөнхийлөгч дайрч өнгөрөх бол, "CAN"(хашилтгүйгээр) ба засагдах хамгийн бага төлбөрийг зайгаар тусгаарлан хэвлэнэ.

Хэрвээ уг замыг ерөнхийлөгч ашиглахаар байлгаж чадахгүй бол "NO"(хашилтгүйгээр) хэвлэнэ.

Орчуулсан: Баттулга

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

Оролт
6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1
Гаралт
YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES
Оролт
3 3 1 3
1 2 10
2 3 10
1 3 100
Гаралт
YES
YES
CAN 81
Оролт
2 2 1 2
1 2 1
1 2 2
Гаралт
YES
NO

Тэмдэглэл

Зам засах зардал нь тухайн замыг засахаас өмнөх түүгээр аялаж байсан хугацаа ба засварын дараах түүгээр аялаж байгаа хугацааны зөрүү.

Эхний жишээн дээр ерөнхийлөгч дараах хоёр замыг аль нэгийг сонгож явах боломжтой: $1 -> 2 -> 4 -> 5 -> 6$ эсвэл $1 -> 2 -> 3 -> 5 -> 6$.

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