Hẳn các bạn đã biết ngày "ông Ngâu bà Ngâu" hàng năm, đó là một ngày đầy mưa và nước mắt. Tuy nhiên, một ngày trước đó, nhà Trời cho phép ~2~ "ông bà" được đoàn tụ. Trong vũ trụ vùng thiên hà nơi ông Ngâu bà Ngâu ngự trị có ~N~ hành tinh đánh số từ 1 đến N, ông ở hành tinh Adam (có số hiệu là ~S~) và bà ở hành tinh Eva (có số hiệu là ~T~). Họ cần tìm đến gặp nhau. ~N~ hành tinh được nối với nhau bởi một hệ thống cầu vồng. Hai hành tinh bất kỳ chỉ có thể không có hoặc duy nhất một cầu vồng (hai chiều) nối giữa chúng. Họ luôn đi tới mục tiêu theo con đường ngắn nhất. Họ đi với tốc độ không đổi và nhanh hơn tốc độ ánh sáng. Điểm gặp mặt của họ chỉ có thể là tại một hành tinh thứ ~3~ nào đó.
Yêu cầu:
Hãy tìm một hành tinh sao cho ông Ngâu và bà Ngâu cùng đến đó một lúc và thời gian đến là sớm nhất. Biết rằng, hai người có thể cùng đi qua một hành tinh nếu như họ đến hành tinh đó vào những thời điểm khác nhau
Dữ liệu vào:
- Dòng đầu là ~4~ số ~N~, ~M~, ~S~, ~T~ (~N \le 100~, ~1 \le S ≠ T \le N~), ~M~ là số cầu vồng.
- ~M~ dòng tiếp, mỗi dòng gồm ba số nguyên ~I~, ~J~, ~L~ thể hiện có cầu vồng nối giữa hai hành tinh ~I~ và ~J~ có độ dài là ~L~ (~1 \le I ≠ J \le N~, ~0 < L \le 200~).
Dữ liệu ra
- Do tính chất cầu vồng, mỗi năm một khác, nên nếu như không tồn tại hành tinh nào thoả mãn yêu cầu thì ghi ra một dòng chữ CRY. Nếu có nhiều hành tinh thoả mãn thì ghi ra hành tinh có chỉ số nhỏ nhất.
Ví dụ
Dữ liệu vào
4 4 1 4
1 2 1
2 4 1
1 3 2
3 4 2
Dữ liệu ra
2
Comments