اکبر یک بازی Crawler Dugeon جدید به اسم Keys! خریده است. او آن قدر معتاد این بازی شده است که چندین ساعت به طور متوالی آن را بازی کرده است.

هر Dungeon این بازی به این صورت است که از تعداد $n$ اتاق و $n-1$ در تشکیل شده است. با توجه به این که این اتاق‌ها باید همبند باشند، گراف ارتباط بین این اتاق‌ها باید به صورت درخت باشد. توجه کنید که منظور از گراف ارتباط‌ها گرافی است که رئوس آن متناظر با اتاق‌ها و هر یال آن معادل در بین دو اتاق است.

بازی از اتاق $s$ شروع می‌شود، و اکبر باید به اتاق $t$ برود که ورودی Dungeon بعدی است.

اما $m$ تا از این در‌ها قفل هستند که کلید‌های آن‌ها می‌توانند در اتاق‌های دیگری باشند. شخصیت اکبر در بازی تنها توانایی حمل یک کلید را دارد و اگر کلیدی را برداشت، تا زمانی که در متناظر با آن کلید را باز نکند نمی‌تواند آن کلید را زمین بگذارد.

همچنین 1 ثانیه طول می‌کشد که شخصیت اکبر از یک اتاق به اتاق مجاورش برود. توجه کنید که اگر یک در را با کلید باز کنیم، شخصیت اکبر به اتاق بعدی نمی‌رود و در همان اتاق باقی می‌ماند؛ این فرایند، زمان نمی‌برد و بلافاصله انجام می‌شود. رکورد اکبر در این بازی در واقع مدت زمانی است که طول می‌کشد از $s$ به $t$ برود.

اکبر که خیلی این بازی را دوست دارد، دلش می‌خواهد که رکورد جهانی این بازی را بزند! برای همین از شما خواسته برنامه‌ای بنویسید که با ورودی گرفتن درخت مربوط به Dungeon و اطلاعات کلید‌ها، کمینه زمان مورد نیاز برای رفتن به Dungeon بعدی را خروجی بدهد.

در خط اول $n$ آمده است، که تعداد اتاق‌های Dungeon اکبر را مشخص می‌کند.

در خط بعدی اعداد $s$ و $t$ آمده‌اند، که به ترتیب مربوط به اتاق شروع Dungeon و اتاق ورودی Dungeon بعدی است.

در $n-1$ خط بعدی، اطلاعات مربوط به در‌ها و کلید‌ها به صورت $u\:v\:w$ آمده است که به این معنی است یک در بین اتاق $u$ و $v$ وجود دارد. همچنین اگر $w=0$ باشد، به این معنی است که این در قفل نیست و در غیر این صورت به این معنی است که این در قفل است و کلید آن در اتاق $w$ قرار دارد.

در تنها خط خروجی، کمینه زمان مورد نیاز اکبر برای این که از $s$ به $t$ برود را چاپ کنید.

• زیرمسئله اول (۲۳ نمره): $n \le 100\ 000,\ m \le 8$
• زیرمسئله دوم (۳۶ نمره):$n \le 7000$
• زیرمسئله سوم (۴۱ نمره):بدون محدودیت اضافی

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \leq n \leq 10^6$
• $1 \le s,t,u,v \le n$
• $0 \le w \le n$
• $0 \leq m \leq 20$

• سوال بعد