Mô tả và yêu cầu

ÔNG NGÂU BÀ NGÂU

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 Trong file văn bản OBNGAU.INP gồm
Dòng đầu là 4 số N M S T (N ≤ 100, 1 ≤ S ≠ T ≤ N), M là số cầu vồng.
M dòng tiếp, mỗi dòng gồm hai số I J L thể hiện có cầu vồng nối giữa hai hành tinh
I , J và cầu vồng đó có độ dài là L (1 ≤ I ≠ J ≤ N, 0 < L ≤ 200).
Kết quả Ra file văn bản OBNGAU.OUT, 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ụ

OBNGAU.INP                   OBNGAU.OUT
                         4 4 1 4                       2
                         1 2 1
                         2 4 1
                         1 3 2
                         3 4 2