Trong mạng lưới đường ống dẫn dầu có ~n~ trạm điều áp, đánh số từ 1 đến ~n~ và có ~m~ đoạn đường ống, mỗi đoạn nối 2 trạm điều áp (~2 \le n, m \le 10^5~). Mạng có tính liên thông, tức là giữa hai trạm điều áp bao giờ cũng có đường ống nối với nhau (trực tiếp hoặc qua các trạm khác). Một đoạn đường ống được gọi là trục nếu nó hỏng thì hệ thống mất liên thông. Trong hệ thống mà chúng ta đang xét có ít nhất một đoạn đường trục.

Do tính chất quan trọng của đường trục nên chúng được ưu tiên trong công tác duy tu bảo dưỡng. Người ta chế tạo 2 rô bốt phục vụ kiểm tra đường trục. Khi được lệnh kiểm tra 2 rô bốt (có thể đang ở những trạm khác nhau) sẽ lựa chọn một đoạn đường trục và đồng thời chuyển động tập kết tới hai đầu của đoạn đường trục này, mỗi rô bốt tới một đầu của đoạn trục. Rô bốt chuyển động theo đường ống, mỗi đơn vị thời gian đi được một đơn vị độ dài. Thời gian tập kết là thời gian cần thiết để rô bốt đến sau tới được vị trí tập kết của mình. Rô bốt luôn lựa chọn đoạn đường trục cho thời gian tập kết là nhỏ nhất.

Yêu cầu: Cho cấu hình của mạng, các trạm ~u, v~ đang giữ rô bốt. Hãy xác định thời gian tập kết.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~;
• Mỗi dòng trong ~m~ dòng sau chứa 3 số nguyên ~x, y~ và ~d~ xác định đoạn đường ống độ dài ~d~ nối 2 trạm ~x~ và ~y~;
• Dòng cuối cùng chứa 2 số nguyên ~u~ và ~v~.

Output

• Một số nguyên – thời gian tập kết.

Sample Input 1

8 11
1 2 3
1 3 5
1 4 8
2 4 3
3 4 4
4 5 2
5 6 9
5 7 3
6 7 4
6 8 5
7 8 6
3 6

Sample Output 1

7