#1086. SHORTEST - Đường đi ngắn nhì

Cho đồ thị có hướng gồm đỉnh, cung (có trọng số là độ dài cung). Bạn hãy tìm độ dài đường đi ngắn thứ nhì từ đến (có độ dài ngắn thứ nhì, khác độ dài đường đi ngắn nhất).

Dữ liệu vào:

• Dòng đầu chứa hai số
• dòng tiếp theo, mỗi dòng ghi số nguyên dương tương ứng là có đường đi một chiều từ đến và độ dài bằng .

Dữ liệu ra:

• Một số duy nhất là độ dài đường đi ngắn nhì, nếu không có thì ghi

Ví dụ:

Dữ liệu vào:

4 6
1 2 5
1 3 5
2 3 1
2 4 5
3 4 5
1 4 13

Dữ liệu ra:

11

Giải thích:

• Đường đi ngắn nhất: hoặc độ dài
• Đường đi ngắn nhì: độ dài .