THỰC HÀNH

Một mê cung gồm n địa điểm đánh số từ 1 tới n và m con đường đánh số từ 1 tới m. Con đường thứ i cho phép đi từ địa điểm uᵢ tới địa điểm vᵢ theo một chiều, độ dài con đường là wᵢ. Ban đầu cả n địa điểm đều bị khóa. Khi một địa điểm bị khóa, nó sẽ không cho phép đi ra hay đi vào theo bất cứ con đường nào liên thuộc với nó. Ngược lại khi một địa điểm được mở khóa, người ta có thể thoái mái ra vào nó bằng bất kỳ con đường nào (tất nhiên vẫn phải đi theo chiều đã định của các con đường, không được đi ngược chiều).

Giáo sư X được một nhà thám hiểm Y nhờ dùng máy tính mở khóa để thám hiểm mê cung. Hai người trao đổi qua các thông điệp thuộc một trong hai dạng:

• Giáo sư X : Địa điểm i vừa được mở khóa;
• Nhà thám hiểm Y : Bây giờ có thể đi từ s tới t hay không? Nếu đi được thì độ dài con đường ngắn nhất là bao nhiêu?

Yêu cầu: Biết được k thông điệp và trình tự của chúng, hãy giúp giáo sư X trả lời tất cả câu hỏi của nhà thám hiểm Y.

Dữ liệu vào:

• Dòng đầu chứa ba số nguyên dương n ≤ 300, m, k ≤ 10⁵;
• m dòng tiếp theo, dòng thứ i chứa ba số nguyên dương uᵢ, vᵢ, wᵢ (∀i: wᵢ ≤ 10⁶);
• k dòng tiếp theo, mỗi dòng chứa một thông điệp, đầu dòng là ký tự ∈ {X, Y} cho biết đó là thông điệp của giáo sư X hay nhà thám điểm Y. Nếu là thông điệp của giáo sư X, tiếp theo là số nguyên i cho biết địa điểm i vừa được mở khóa. Nếu là thông điệp của nhà thám hiểm Y, tiếp theo là hai số nguyên s, t ứng với câu hỏi hiện giờ có thể đi từ s tới t hay không?

Dữ liệu ra:

• Với mỗi câu hỏi của nhà thám hiểm Y, ghi ra trên một dòng độ dài đường đi ngắn nhất từ s tới t (nếu hiện tại chưa thể đi từ s tới t, in ra trên dòng số -1).

Ví dụ:

Dữ liệu vào:

5 5 7
1 2 10
3 1 20
2 4 30
2 5 40
3 2 50
X 1
X 4
X 2
Y 1 4
X 3
Y 3 4
Y 5 3

Dữ liệu ra:

40
60
-1