Sau vụ nổ tại tòa tháp Piltover, Jinx bị thương và đang lẩn trốn tại các khu ổ chuột của Zaun. Để hồi phục và chế tạo vũ khí mới, cô cần di chuyển đến xưởng phế liệu bí mật của mình ở Thành phố Bilgewater (một hòn đảo xa).

Tuy nhiên, hành trình vượt biển không hề đơn giản. Jinx phải di chuyển qua mạng lưới các Bến Cảng Ngầm và Đảo Nhỏ do các băng đảng và hải quái kiểm soát. Mỗi tuyến đường di chuyển giữa hai địa điểm đều có một trọng số nhất định, đại diện cho lượng Hextech Gemstone (đá Hextech) cần tiêu hao để tăng tốc tàu, mua chuộc hải tặc hoặc kích hoạt lá chắn tàng hình vượt qua vùng biển nguy hiểm.

Là một kẻ "điên nhưng có nguyên tắc", Jinx muốn tìm ra con đường tiêu tốn ít Đá Hextech nhất để đến được Bilgewater, nhằm dành dụm tối đa năng lượng cho khẩu Cá Mập Nổ (Fishbones) của mình.

Dữ liệu vào:

• Dòng đầu tiên chứa 3 số nguyên ~N~ (số địa điểm), ~M~ (số tuyến đường biển), ~S~ (điểm bắt đầu ở Zaun).
• Dòng thứ hai chứa tên điểm đích ~D~ (luôn là chuỗi "Bilgewater").
• ~M~ dòng tiếp theo, mỗi dòng mô tả một tuyến đường: ~U V W~ (Xuất phát từ ~U~, đến ~V~, tiêu hao ~W~ đá Hextech).
• Tên địa điểm là các chuỗi ký tự không có dấu cách (Ví dụ: Piltover, Bilgewater, Zaun, ShadowIsles...).

Kết quả:

• Một số nguyên duy nhất là tổng số đá Hextech ít nhất Jinx phải tiêu hao.
• Nếu không thể đến được Bilgewater, in ra Jinx khong the den duoc Bilgewater!~.

Input

5 6 Zaun
Bilgewater
Zaun Piltover 5
Zaun Ionia 10
Piltover Bilgewater 15
Ionia ShadowIsles 2
ShadowIsles Bilgewater 4
Piltover ShadowIsles 8

Output

16

Giải thích

• Jinx xuất phát từ Zaun.
• Có hai tuyến chính để đến Bilgewater:
  1. Zaun -> Piltover -> Bilgewater: ~5 + 15 = 20~ đá.
  2. Zaun -> Ionia -> ShadowIsles -> Bilgewater: ~10 + 2 + 4 = 16~ đá.
• Tuyến thứ hai tuy vòng vèo hơn nhưng lại tiết kiệm Đá Hextech hơn (~16 < 20~). Jinx sẽ chọn tuyến này.

Ràng buộc:

• ~1 \leq N \leq 10^5~ (Số lượng địa điểm có thể rất lớn, bao gồm tên như Demacia, Noxus, Freljord, Bilgewater...)
• ~0 \leq W \leq 10^4~
• Đồ thị có hướng hay vô hướng tùy bạn chọn (nên là vô hướng vì tàu biển đi lại được hai chiều).