Tima Xentopiába utazik

A kép forrása: WikiImages.

Xentopia városa kiterjedt vasúthálózattal rendelkezik. A városban N csomópont van, amelyeket 1-től N-ig számozunk. A csomópontokat M sínpár köti össze egymással. Minden sínpáron mindkét irányban közlekedhetnek a vonatok. Az egyes sínpárokat piros, kék vagy fehér színnel címkézzük.

Tima egy turista a városban, aki a lehető legrövidebb idő alatt szeretne eljutni az S csomópontból a T csomópontba. A célja eléréséhez használhatja a vasúthálózat térképét.

Tima meglehetősen excentrikus személyiség, ezért szabott magának egy érdekes feltételt: pontosan k₁ piros, k₂ kék és tetszőleges számú fehér sínpár igénybevételével szeretne utazni. A különböző színű sínpárok sorrendje tetszőleges lehet, és ugyanazt a sínpárt többször is felhasználhatja.

A feladatod, hogy meghatározd azt a minimális időt, amennyi ahhoz szükséges, hogy Tima eljusson S-ből T-be az általa szabott feltétel betartásával.

A bemenet specifikációja

A bemenet első sorában négy, szóközzel elválasztott egész szám szerepel: N (1 ≤ N ≤ 450), M (1 ≤ M ≤ 1 100), k₁ és k₂ (0 ≤ k₁, k₂ ≤ 800, k₁ · k₂ ≤ 800). Ezt M sor követi, amelyek mindegyike szintén négy, szóközzel elválasztott egész számot tartalmaz U V X C formában, ahol U és V két olyan csomópont, amelyek között létezik sínpár (1 ≤ U, V ≤ N, U ≠ V), ezt a távolságot a vonat X másodperc alatt teszi meg (0 ≤ X ≤ 10⁹), és a sínpár C színnel van címkézve (0 ≤ C ≤ 2). Fehér sínpár esetén C = 0, piros sínpár esetén C = 1, míg kék sínpár esetén C = 2.

Az utolsó sorban két, szóközzel elválasztott egész szám szerepel: S (1 ≤ S ≤ N) és T (1 ≤ T ≤ N), amelyek rendre Tima utazásának forrás és cél csomópontját adják meg. Megjegyezzük, hogy S és T azonosak is lehetnek.

A kimenet specifikációja

A kimenetre egyetlen egész számot kell kiírni, amely Tima utazásának összidejét adja meg. Ha Tima nem tud eljutni a célba pontosan k₁ piros, k₂ kék és tetszőleges számú fehér sínpáron keresztül, akkor –1-et kell kiírni.