#1145. DRAGON - Đảo rồng

Đất nước HP xinh đẹp là một quần đảo gồm đảo đánh số từ đến , có đường bay hai chiều giữa các đảo được đánh số từ đến , đường bay thứ nối hai đảo và có độ dài .

Việc di chuyển giữa các đảo không thực hiện bằng máy bay như bình thường mà bay bằng rồng. Mỗi đảo có một con rồng, con rồng ở đảo có thể bay được một quãng đường xa nhất là (gọi là sức bay), như vậy để con rồng ở đảo bay được trên con đường (nối đảo với một đảo khác) thì .

Khi di chuyển từ đảo đến đảo , để tiếp tục chuyến bay, bạn có thể sử dụng con rồng đang dùng hoặc đổi sang con rồng ở đảo .

Hoàng tử Dương Phong đang sống ở đảo số , anh ấy muốn biết hai thông tin sau để chuẩn bị cho chuyến du lịch của mình:

• Xuất phát từ đảo , anh ấy sử dụng con rồng tại đảo , không đổi rồng trong suốt hành trình thì anh ấy có thể gặp con rồng có sức bay lớn nhất là bao nhiêu?
• Xuất phát từ đảo , có thể đổi rồng trên đường đi thì độ dài đường đi ngắn nhất từ đến là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương tương ứng là câu hỏi và là câu hỏi ;
• Dòng tiếp theo chứa hai số nguyên dương theo thứ tự là số lượng đảo và số đường bay hai chiều;
• Dòng tiếp theo ghi số nguyên dương, số thứ là tương ứng là sức bay của con rồng ở đảo ;
• dòng tiếp theo, dòng thứ chứa ba số nguyên tương ứng là có đường bay nối hai đảo và độ dài .

Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

• Nếu thì ghi kết quả của câu hỏi , nếu thì ghi kết quả của câu hỏi ; Với câu hỏi , dữ liệu đảm bảo có thể bay từ đến và độ dài đường đi ngắn nhất là số nguyên không quá

Ví dụ:

Dữ liệu vào:

1
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14

Dữ liệu ra:

20

Giải thích:

• : từ đảo thực hiện chuyến bay mà không đổi rồng ở các đảo thì ta có thể đi: . Vậy Dương Phong có thể gặp con rồng ở đảo có sức bay lớn nhất là

Dữ liệu vào:

2
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14

Dữ liệu ra:

28

Giải thích:

• : từ đảo thực hiện chuyến bay đến đảo .
  • : sử dụng rồng , quãng đường ;
  • : sử dụng rồng , quãng đường , đổi rồng;
  • : sử dụng rồng , quãng đường ;
  • : sử dụng rồng , quãng đường .
• Tổng độ dài đường đi ngắn nhất là: .

Giới hạn:

• Câu hỏi ứng với được số điểm của bài toán
• Câu hỏi ứng với được số điểm của bài toán.