#599. AIRLINES - Tuyến bay

Có thành phố và đường hàng không hai chiều giữa một số cặp thành phố nào đó, các đường bay được quản lý bởi hãng hàng không. Các thành phố được đánh số từ tới và các hãng được đánh số từ tới .

Được biết chi phí bay trực tiếp giữa hai thành phố bất kỳ (nếu như có đường bay là . Nếu đang đi máy bay của một hãng đến sân bay nào đó rồi chuyển sang máy bay của hãng khác thì sẽ phải mất thêm một khoản phụ phí .

Yêu cầu: Cho trước hai thành phố và , hãy tìm hành trình bay từ thành phố đến thành phố với chi phí ít nhất. Với giả thiết rằng luôn luôn tồn tại cách bay từ tới .

Dữ liệu vào:

• Dòng đầu ghi sáu số nguyên dương ;
• dòng tiếp theo, mỗi dòng có dạng cho biết rằng giữa thành phố và thành phố có đường bay của hãng .

Dữ liệu ra:

• Dòng đầu ghi chi phí tối thiểu phải trả;
• Các dòng tiếp theo, mỗi dòng ghi một bộ ba thể hiện tại bước đó sẽ bay từ thành phố đến thành phố bởi máy bay của hãng . Thứ tự các dòng phải theo đúng thứ tự bay trong hành trình.

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

Ví dụ:

Với mạng lưới đường không như hình trên: cần đi từ thành phố đến thành phố . Chi phí đường bay trực tiếp giữa hai thành phố bất kỳ , phụ phí chuyển tuyến . Các số ghi bên cạnh các đường bay trực tiếp là tên các hãng sở hữu đường bay đó.

Dữ liệu vào:

15 20 3 2 1 5
1 2 1
2 3 1
3 4 1
3 4 2
3 9 2
4 9 1
5 10 1
5 10 3
6 7 1
6 11 1
7 8 1
7 13 2
8 9 1
10 15 3
11 12 1
12 13 1
13 14 1
13 14 3
14 15 1
14 15 3

Dữ liệu ra:

37
1 2 1
2 3 1
3 4 1
4 9 1
9 8 1
8 7 1
7 13 2
13 14 3
14 15 3
15 10 3
10 5 3