Trước kia Tý và Tèo là hai bạn cùng lớp còn bây giờ hai bạn học khác trường nhau. Cứ mỗi sáng, đúng 6 giờ cả hai chỉ đi từ nhà tới trường của mình theo con đường mất ít thời gian nhất. Hôm nay, Tý muốn gặp Tèo trên đường đi học. Tý và Tèo có thể gặp nhau tại một nút giao thông nào đó nếu họ đến nút giao thông này tại cùng một thời điểm.

Cho biết sơ đồ giao thông của thành phố gồm N nút giao thông được đánh số từ 1 đến N và M tuyến đường phố (mỗi đường phố nối 2 nút giao thông). Biết rằng nhà của Tý và Tèo cũng như trường của hai bạn đều nằm ở các nút giao thông. 

Yêu cầu: Hãy tìm thời gian sớm nhất mà Tý và Tèo có thể gặp nhau trên đường đi học.

Dữ liệu: Vào từ tệp văn bản test.inp gồm:

• Dòng 1: Ghi số nguyên dương N, M (1 ≤ N, M ≤ 100).
• Dòng 2: Ghi 4 số nguyên dương Ha, Sa, Hb, Sb lần lượt là số hiệu các nút giao thông tương ứng với: Nhà Tý, trường của Tý, nhà Tèo, trường của Tèo.
• Dòng thứ i trong số M dòng tiếp theo chứa ba số nguyên dương Ai, Bi, Ti. Với Ai và Bi là hai đầu của tuyến đường phố i. Còn Ti là thời gian đi từ Ai đến Bi cũng như từ Bi đến Ai (Ti ≤ 100, Ti tính bằng phút).

Giả sử sơ đồ giao thông trong thành phố đảm bảo để có thể đi từ một nút giao thông bất kỳ đến tất cả các nút còn lại.

Kết quả: Ghi ra tệp văn bản test.out thời gian sớm nhất mà Tý và Tèo có thể gặp nhau theo cách đi như trên. Nếu hai bạn không gặp nhau trên đường đi thì ghi ra -1.