Несправні компоненти
Будучи членом журі конкурсу "Найкращий архітектурний конкурс", вам доручено оцінити надійність системи. Усі системи, що беруть участь у конкурсі, складаються з ряду компонентів, які залежать один від одного. Надійність такої системи визначається шкодою, завданою несправним компонентом. Ідеально, щоб несправний компонент не мав жодних наслідків, але оскільки більшість компонентів взаємозалежні, деякі інші компоненти також зазвичай виходять з ладу.
Більшість компонентів стійкі до короткочасних відмов компонентів, від яких вони залежать. Наприклад, база даних може бути недоступна за хвилину до закінчення терміну дії кешу, і нові дані повинні бути отримані з бази даних. У цьому випадку кеші можуть функціонувати протягом хвилини після збою бази даних, перш ніж самі стануть непридатними. Якщо компонент залежить від інших компонентів, які виходять з ладу, то він також вийде з ладу. Крім того, компонент не залежить безпосередньо від себе, однак можлива непряма самозалежність через інші компоненти.
Ви хочете дізнатися, скільки компонентів зазнає невдачі, якщо якийсь компонент зламається, і скільки часу мине до того, як усі компоненти, які врешті-решт зазнають невдачі, дійсно стануть непридатними. Це складно розрахувати вручну, тому ви вирішили написати програму, яка допоможе вам. За описом системи та початковим зламаним компонентом програма повинна повідомити, скільки компонентів врешті-решт зазнає невдачі, і скільки часу мине, перш ніж усі ці компоненти дійсно стануть непридатними.
Вхідні дані
Перший рядок містить кількість тестів, не більше 100. Далі для кожного тесту:
перший рядок містить три цілих числа n, d і c (1 ≤ n ≤ 10 000, 1 ≤ d ≤ 100 000, 1 ≤ c ≤ n): загальна кількість компонентів у системі, число залежностей між компонентами і номер компонента, який спочатку виходить з ладу.
d рядків, що містять по три цілих числа a, b і s (1 ≤ a, b ≤ n і a ≠ b і 0 ≤ s ≤ 1000), вказуючи на те, що компонент a залежить від компонента b, і здатний працювати ще s секунд після збою b.
У кожному тесті всі залежності (a, b) унікальні.
Вихідні дані
Для кожного тесту виведіть в окремому рядку два цілих числа: загальна кількість компонентів, які стануть несправними, і кількість секунд до того, як усі компоненти, які будуть ламатися, стануть повністю непридатними.