Дорога#6576
В одній країні є міст, пронумерованих від до . Інженер-будівельник повинен звести мережу доріг загального користування, яка з'єднає всі міста, тобто має існувати можливість дістатися з будь-якого міста в будь-яке інше, можливо, через проміжні міста. Його команда обстежила кілька маршрутів (дороги між парами міст). Кожна дорога є двосторонньою. Будівництво дороги вимагає певних витрат: чим коротший маршрут, тим дешевше будівництво.
Інженер ніколи заздалегідь не проектував дорожню систему. Він просто обирає вподобану дорогу і будує її, поки всі міста не будуть з'єднані.
Тепер інженер хоче побудувати дорогу між містами і . Під тиском уряду, який прагне скоротити витрати, він просить вас написати програму, яка визначить, чи варто будувати цю дорогу. Ваша програма має вивести "YES", якщо після будівництва дорога увійде до мінімальної дорожньої системи, що з'єднує всі міста. В іншому випадку слід вивести "NO".
Перший рядок містить кількість тестів t~(t \le 10).
Кожен тест починається з рядка з цілих чисел n, m, p і . Тут n~(2 \le n \le 10000) — кількість міст, m~(1 \le m \le 20000) — число доріг, а та q~(1 \le p, q \le n) задають міста, між якими інженер збирається побудувати дорогу.
Далі слідують рядків, кожен з яких містить три числа і w~(1 \le u, v \le n, 1 \le w \le 4 \cdot 10^5), що описують існуючу двосторонню дорогу довжиною між містами і . Довжини всіх доріг різні. Між будь-якою парою міст може існувати не більше однієї дороги. Гарантується, що граф зв'язний, тобто між будь-якою парою міст існує шлях. Всі числа цілі.
Для кожного тесту виведіть "YES", якщо дорога буде входити до мінімальної дорожньої системи. В іншому випадку виведіть "NO".
Приклад 1