Bessie chuyển nhà đến một trang trại nhỏ, nhưng cô ấy thường xuyên quay lại trang trại của FJ để thăm bạn bè. Bessie rất thích phong cảnh ven đường và không muốn kết thúc chuyến đi quá nhanh, vì vậy mỗi lần về trang trại, cô ấy đều chọn đường đi ngắn thứ hai, thay vì chọn đường ngắn nhất như chúng ta thường làm.
Vùng quê nơi Bessie sống có con đường hai chiều, mỗi con đường nối hai trong số trang trại. Bessie sống ở trang trại , và bạn bè cô ấy sống ở trang trại (đây là đích đến mỗi chuyến đi của Bessie).
Đường đi ngắn thứ hai mà Bessie chọn có thể bao gồm bất kỳ con đường nào xuất hiện trong đường đi ngắn nhất, và một con đường có thể được đi lại nhiều lần. Tất nhiên, độ dài của đường đi ngắn thứ hai phải lớn hơn nghiêm ngặt độ dài của đường đi ngắn nhất (có thể có nhiều đường ngắn nhất), nhưng độ dài của nó phải không lớn hơn độ dài của bất kỳ đường đi nào khác ngoại trừ các đường đi ngắn nhất.
Tóm tắt đề bài: Cho một đồ thị vô hướng, tìm độ dài của đường đi ngắn thứ nhì nghiêm ngặt (strictly second shortest path) của đồ thị.
Dữ liệu:
Dòng 1 của file đầu vào chứa hai số nguyên và , cách nhau bởi dấu cách;
Dòng : Mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách và , biểu thị tồn tại một con đường có độ dài nối trang trại và trang trại .
Kết quả:
Xuất ra duy nhất một số nguyên, biểu thị độ dài của đường đi ngắn thứ hai từ trang trại đến trang trại .
