#1242. ICBUS - Xe liên tỉnh

Quốc gia Backoi có thành phố, mỗi thành phố có một hệ thống xe chạy liên tỉnh khác nhau. Một xe có thể chạy từ thành phố sang thành phố nếu như có đường nối trực tiếp giữa hai thành phố này.

Các con đường ở đây đều là đường chiều. Mỗi hệ thống xe liên tỉnh có một số luật như sau:

• Hành khách muốn sử dụng hệ thống xe của thành phố thì bắt buộc phải bắt xe tại thành phố ;
• Giá vé xe của thành phố là đồng hạng bất kể quãng đường bao xa;
• Hệ thống xe của thành phố chỉ cho phép chạy tối đa qua thành phố.

Quân là một hành khách muốn đi từ thành phố đến thành phố . Hãy giúp Quân tìm cách đi sao cho tổng chi phí là thấp nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương và ;
• dòng tiếp theo, dòng thứ chứa hai số nguyên dương và là hai thông tin của hệ thống xe của thành phố ;
• dòng tiếp theo mỗi dòng ghi hai số và biểu thị giữa hai thành phố và có đường nối trực tiếp.

Dữ liệu ra:

• Ghi ra duy nhất một số là chi phí Quân phải trả để đi từ thành phố đến thành phố . Dữ liệu đảm bảo luôn có cách đi từ thành phố đến thành phố .

Ví dụ

Dữ liệu vào:

6 6
400 2
200 1
500 3
900 1
400 4
200 5
1 2
1 5
2 3
2 4
3 6
4 6

Dữ liệu ra:

800

Giải thích:

• Quân sử dụng lần lượt hệ thống xe của thành phố rồi thành phố .