Пункт призначення невідомий
Ви агент B100. Пара яскраво одягнених циркових артистів подорожує дорогами міста, і ваше завдання — з'ясувати, куди вони прямують. Відомо лише, що вони стартували з точки s і прямують до одного з кількох можливих місць призначення. Вони дуже поспішають, тому ми впевнені, що не будуть робити обхід до свого місця призначення.
На жаль, хоч вони і яскраво одягнені, дует ніде не видно. На щастя, у вас є виняткове чуття. Зокрема, ваш ніс ніколи вас не підводить. Ви можете відчути, що вони подорожували дорогою між перехрестями g та h.
Куди прямує невловимий дует? Чи ми все ще не впевнені?
Візуальне представлення другого прикладу. Дует подорожує від сірого кола до одного з двох чорних кіл, і ви відчули їх на пунктирній лінії, тому вони можуть прямувати до 6.
Вхідні дані
На першому рядку одне додатне число: кількість тестових випадків, не більше 100. Після цього для кожного тестового випадку:
Один рядок з трьома цілими числами, розділеними пробілами: n, m та t (2 ≤ n ≤ 2000, 1 ≤ m ≤ 50000 та 1 ≤ t ≤ 100): кількість перехресть у місті, кількість окремих доріг між цими перехрестями та кількість можливих місць призначення відповідно.
Один рядок з трьома цілими числами, розділеними пробілами: s, g та h (1 ≤ s, g, h ≤ n): перехрестя, з якого дует почав, і два перехрестя, між якими дует подорожував, при цьому g ≠ h.
m рядків з трьома цілими числами, розділеними пробілами: a, b та d (1 ≤ a < b ≤ n та 1 ≤ d ≤ 1000), що вказують на те, що між перехрестями a та b є двостороння дорога довжиною d.
t рядків з одним цілим числом x (1 ≤ x ≤ n): можливі місця призначення. Усі можливі місця призначення є різними і всі вони відрізняються від s.
Між парою перехресть є не більше однієї дороги. Один з m рядків описує дорогу між g та h. Ця дорога гарантовано знаходиться на найкоротшому шляху до принаймні одного з можливих місць призначення.
Вихідні дані
Для кожного тестового випадку:
Один рядок з одним або більше цілими числами, розділеними пробілами, що вказують на місця призначення, до яких дует все ще може прямувати, у зростаючому порядку.