Archiwum zadań programistycznych WWSI

Czy wiecie, że w rankingu najbardziej zakorkowanych miast Europy na pierwszym miejscu znajduje się Bruksela? Nie byłoby nic niepokojącego gdyby nie fakt, że miejsca 2 i 3 zajmują odpowiednio Warszawa i Wrocław. Jak już wiadomo najbliższe Akademickie Mistrzostwa Polski w Programowaniu Zespołowym odbędą się właśnie w Warszawie. Stan dróg tego miasta rodzi poważne obawy organizatorów. W związku z tym wystąpili oni z prośbą do Ciebie o napisanie programu, który na podstawie opisu sieci dróg oraz ilości samochodów na poszczególnych skrzyżowaniach obliczy najmniej zakorkowaną trasę z hotelu do miejsca, w którym odbędą się zawody.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 10) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

Pierwsza linia każdego zestawu danych zawiera cztery liczby całkowite n, m, a, b (1 ≤ n ≤ 1000; (n - 1) ≤ m ≤ (n × (n - 1)) / 2; 1 ≤ a, b ≤ n i a ≠ b) oznaczające odpowiednio ilość skrzyżowań i łączących je dróg oraz numer skrzyżowania początkowego i końcowego. W kolejnych m liniach znajduje się opis dróg łączących skrzyżowania. Opis każdej drogi składa się z czterech liczb całkowitych c, d, s, t (1 ≤ c, d ≤ n; 0 ≤ s ≤ 10⁶; 1 ≤ t ≤ 2). Liczby c i d określają, że jest to droga łącząca skrzyżowania c i d. Liczba s określa stan zakorkowania drogi, zaś liczba t jej rodzaj: 1 - ulica jednokierunkowa, 2 - ulica dwukierunkowa. Zapis 5 8 100 2 oznacza, że skrzyżowanie 5 połączone jest z 8 dwukierunkową ulicą, a w korku stoi 100 samochodów. Dla uproszczenia zakładamy, że korek w obydwie strony jest takiej samej długości.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać jedną liczbę całkowitą określającą minimalną sumaryczną długość korka w jakim trzeba odstać, aby dojechać z punktu początkowego do końcowego.

Przykład

Wejście:

1
6 9 1 4
1 2 50 1
1 6 8 1
2 3 90 2
2 6 4 2
2 5 8 1
6 5 100 2
3 5 80 1
3 4 10 1
5 4 20 1

Wyjście:

40