Навігація Форпосту
Місто захоплене зомбі, і ви з вашою командою маєте обмежені запаси. Завдяки ретельній розвідці та плануванню, вам надали карту зі списком безпечних постів разом із звітом, що містить кількість зомбі, помічених у цій місцевості. Кожен пост є частиною радіомережі та використовує свій радіопозивний як назву місця розташування.
Ваша команда має обмежену кількість боєприпасів і може відбити лише групи зомбі певного розміру. Кожна одиниця боєприпасів може відбити одного зомбі за одну подорож. Щоб безпечно подорожувати дорогою, ви повинні витратити кількість боєприпасів, що дорівнює кількості зустрічей із зомбі на дорозі. Враховуючи дані розвідки, визначте безпечний шлях до поста, який має необхідні вам запаси, з найменшою кількістю зустрічей із зомбі. Ви почнете свою подорож з першого зазначеного поста і почнете з будь-якими боєприпасами на цьому посту. Може бути до одного іншого поста, який має боєприпаси, але не має необхідних вам запасів. Якщо ви подорожуєте до цього поста, ви можете зібрати всі його боєприпаси. Будь-яка кількість постів може мати необхідні вам запаси, але вам потрібно подорожувати лише до одного з них.
Якщо з будь-якої причини вам потрібно подорожувати дорогою кілька разів, ви зустрінете таку ж кількість зомбі, як і під час першої подорожі, для кожної наступної подорожі, і зомбі враховуються як додаткові зустрічі з зомбі. Зомбі не легко вбити кулями.
Вхідні дані
Перша строка введення міститиме кількість тестових випадків, C (1 ≤ C ≤ 50).
Для кожного тестового випадку буде одна строка, що містить кількість постів, N (1 ≤ N ≤ 100), за якою слідує кількість доріг, R (0 ≤ R ≤ 200).
1 1
Для кожного поста буде одна строка, що містить позивний (6 символів від A-Z та 0-9), за якою слідує кількість боєприпасів на посту A, (0 ≤ A ≤ 100), за якою слідує вказівка, чи є на посту необхідні запаси ("yes" або "no").
CLLSGN 0 yes
Для кожної дороги буде одна строка, що містить позивні 2 постів, які вона з'єднує, за якою слідує кількість зомбі, яких ви зустрінете на дорозі, Z (0 ≤ Z ≤ 100).
OTPST1 OTPST2 5
Вихідні дані
Для кожного тестового випадку надрукуйте одну строку, що містить мінімальну кількість зустрічей із зомбі для безпечного шляху до поста з необхідними запасами. Якщо безпечного шляху до запасів немає, надрукуйте одну строку, що містить рядок "No safe path".