Chuyện hẹn hò

B là anh chàng tài hoa nổi tiếng của trường NAM, G là hoa khôi của trường NỮ. B và G quen nhau đã lâu. Không biết từ lúc nào cả hai đã tuân thủ một qui ước: mỗi chiều đi học về cần gặp nhau tại một địa điểm do G chọn (có thể là rạp chiếu bóng, quán kem hay đơn giản chỉ là góc phố quen) sau đó về thẳng nhà của mỗi người. Nhiệm vụ của B là cần chỉ ra đường đi ngắn nhất cho cả hai người để từ trường đến điểm hẹn sau đó về nhà – dĩ nhiên, B và M đang học 2 trường khác nhau và ở 2 nhà cũng khác nhau. Cả hai đều sinh sống và học tập ở thành phố A. B đang học chuyên ngành CNTT nên quyết định số hóa bản đồ thành phố. Thành phố A có N địa điểm được B đánh số từ 1 đến N, trường NAM là địa điểm U, trường NỮ là địa điểm V, nhà B là địa điểm Z, nhà G là địa điểm T, điểm hẹn là địa điểm X. B cũng đã khảo sát và ghi nhận lại khoảng cách giữa các địa điểm có đường nối cũng như đánh dấu các cặp địa điểm không có đường nối trực tiếp. Bạn hãy giúp B lập trình để có thể xác định đường đi cho B và M sao cho tổng quãng đường cả hai người phải đi qua là bé nhất – vì B chưa học LTĐT.

Dữ liệu vào được cho trong tập tin văn bản HENHO.IN gồm

-          Dòng đầu tiên ghi số nguyên N là số địa điểm của thành phố A (0 < N <= 100).

-          N dòng tiếp theo, mỗi dòng ghi N số thực. Số ở dòng I cột J cho biết khoảng cách đoạn đường nối từ I đến J và được ghi là 0 nếu không có đường nối.

-          Dòng cuối cùng ghi 5 số U, V, Z, T, X

Kết quả tìm được ghi vào tạp tin văn bản HENHO.OUT ghi một số thực là tổng độ dài quảng đường mà B và G phải đi qua và được ghi là -1 nếu không tìm được đường đi thỏa yêu cầu.

Ghi chú: các số trên cùng dòng cách nhau bởi khoảng trắng, các số thực được làm tròn với phần thập phân có 2 chữ số.

Ví dụ: