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: từ tệp văn bản NGAU.INP
gồm
Dòng đầu là 4
số N M S T (N ≤ 1000, 1 ≤ S ≠ T ≤ N), M là số cầu vồng. M dòng tiếp, mỗi dòng
gồm ba 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).
Dữ liệu ra: ghi vào tệp văn bản
NGAU.OUT, 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ụ:
|
NGAU.INP
|
NGAU.OUT
|
|
4 4 1 4
1 2 1
2 4 1
1 3 2
3 4 2
|
2
|
