AlgoLiga 2018

Władze stolicy właśnie dowiedziały się, że w najbliższym czasie planowane jest przejście ogromnej demonstracji. Miasto pełne jest zabytków i starych kamienic, które mogłyby ucierpieć w przypadku zamieszek, ale naszych polityków to nie obchodzi. Jedyne na czym im zależy to, aby demonstracja nie przeszła ulicami, na których znajdują się ratusz oraz sejm. W związku z powyższym urzędnicy negocjują właśnie z organizatorami trasę przemarszu.

Organizatorzy przedstawili sprawę jasno - chcą jedynie dotrzeć z punktu p do punktu k ponosząc przy tym jak najmniejszy koszt (w stolicy organizatorzy demonstracji muszą płacić za możliwość przejścia przez daną ulicę, wyznaczoną przez urząd miasta stawkę). Nic prostszego pomyśleli urzędnicy - wyznaczymy koszty przejścia przez ulice na których są ratusz i sejm w taki sposób, aby demonstracja je ominęła!

Po opracowaniu tej genialnej koncepcji (i otrzymaniu w związku z tym premii) urzędnicy zabrali się za... poszukiwanie osoby, która zrobi wszystko za nich i poprosili nas, aby umieścić to zadanie w AlgoLidze. Ocal polityków przed niechybnym obrzuceniem jajkami! Napisz program, który obliczy o ile należy podnieść koszt przejścia przez chronione ulice, aby zagwarantować, że nie znajdą się one na trasie przemarszu.

Wejście

W pierwszej linii wejścia znajdują się cztery liczby całkowite n, m, p, k (3 ≤ n ≤ 1000; 3 ≤ m ≤ 1500; 0 ≤ p, k < n; p ≠ k) określające odpowiednio liczbę skrzyżowań w mieście, liczbę łączących je ulic oraz numer skrzyżowania początkowego i końcowego trasy demonstracji.

W kolejnych m liniach znajdują się opisy ulic. Każdy opis składa się z trzech liczb a, b, c (0 ≤ a, b < n; a ≠ b; 1 ≤ c ≤ 100) oraz opcjonalnego wyrazu CHRONIONA, który wskazuje na to, że opis dotyczy ulicy, na której znajduje się sejm lub ratusz. Warto tutaj odnotować, że sejm i ratusz mogą znajdować się na tej samej ulicy. Liczby a i b określają numery skrzyżowań pomiędzy, którymi przebiega ulica, zaś liczba c określa stawkę jaką demonstranci muszą zapłacić miastu ze jej przejście.

Uwaga! Gwarantujemy, że jeżeli najtańsza droga z p do k prowadzi przez ulice, na których znajduje się sejm lub ratusz, to będzie istniała, co najmniej jeszcze jedna trasa pomiędzy tymi skrzyżowaniami.

Wyjście

Na wyjściu należy wypisać minimalną sumę kwot o jaką należy podnieść opłaty za przejście ulicami, na których znajduje się sejm i ratusz, tak aby na pewno nie przeszła tamtędy demonstracja.

Przykład

Wejście

8 9 0 7
0 1 1
0 2 1
0 3 1
1 4 1 CHRONIONA
4 7 1
2 5 1 CHRONIONA
5 7 1
3 6 3
6 7 2

Wyjście

8