Світлофори

Кеноша — місто поблизу Фермера Джона, має m доріг (пронумерованих від 1 до m), які з'єднують n перехресть (пронумерованих від 1 до n). Жодні дві дороги не з'єднують одну й ту ж пару перехресть, і жодна дорога не з'єднує перехрестя саме з собою. Час подорожі T[ij] (1 ≤ T[ij] ≤ 100) між перехрестями i та j однаковий в обох напрямках (тобто T[ij] = T[ji]).

Кожне перехрестя має світлофор з двома кольорами: синім або фіолетовим. Колір кожного світла періодично змінюється: синій деякий час, а потім фіолетовий інший час. Рух по дорозі між будь-якими двома перехрестями дозволяється почати лише тоді, коли світлофори на обох перехрестях мають один і той самий колір у момент відправлення. Кольори світлофорів не обов'язково повинні бути однаковими протягом всієї поїздки.

Якщо транспортний засіб прибуває на перехрестя в момент зміни світла, він повинен враховувати нові кольори. Транспортним засобам дозволено чекати на перехрестях. Вам надано карту міста, яка показує:

• Час подорожі T[ij] для всіх доріг

• Тривалість обох кольорів на перехресті i: DB[i] (1 ≤ DB[i] ≤ 100) для синього кольору і DP[i] (1 ≤ DP[i] ≤ 100) для фіолетового

• Початковий колір C[i] світлофора на перехресті i (літера 'B' або 'P') і залишковий час R[i] (1 ≤ R[i] ≤ 100) до зміни кольору

Знайдіть найменший час, за який можна дістатися з перехрестя s (1 ≤ s ≤ n) до перехрестя d (1 ≤ d ≤ n, d ≠ s).

Розглянемо карту з чотирма перехрестями і п'ятьма дорогами. Фермер Джон хоче потрапити з перехрестя 1 на перехрестя 4. Колір на першому перехресті синій, на решті фіолетовий.

Найменший час дорівнює 127, використовуючи шлях 1-2-4.

Спочатку світло на перехресті 1 синє. Оскільки світло на перехресті 2 фіолетове, транспортний засіб чекає на перехресті 1 2 секунди, потім подорожує 4 секунди до перехрестя 2.

У момент 6, світло на перехресті 2 перемикається на синє, тоді як світло на перехресті 4 має ще 32 секунди до перемикання на синє. Однак, після 32 секунд, світло на перехресті 2 перемикається на фіолетове, а світло на перехресті 4 перемикається на синє одночасно. Тому транспортний засіб повинен чекати ще 13 секунд, щоб світло на перехресті 2 перемкнулося на синє, тоді вогні мають однаковий колір, і транспортний засіб подорожує 76 секунд до пункту призначення на перехресті 4.

Загальний час 2 + 4 + 32 + 13 + 76 = 127 секунд.

Нижче представлений план подорожі:

Вхідні дані

Перша стрічка містить два цілих числа s і d.

Друга стрічка містить два цілих числа n (2 ≤ n ≤ 300) і m (1 ≤ m ≤ 14000).

i-ий з наступних n рядків описує перехрестя i символом і трьома цілими числами: C[i], R[i], DB[i] і DP[i].

k-ий з наступних m рядків описує дорогу k трьома цілими числами i, j і T[ij].

Вихідні дані

Виведіть час, витрачений на шлях мінімального часу від початкового перехрестя до кінцевого перехрестя. Якщо шляху немає, виведіть 0.

Приклади