Thành phố bạn Lam sống có n nút giao thông được đánh số từ 1 đến n. Việc đi lại giữa các nút giao thông được thực hiện qua các tuyến xe bus. Có tất cả m tuyến, tuyến thứ i cho phép di chuyển hai chiều từ nút giao thông ai đến bi (ai≠bi) và có tiền vé một lượt đi là c_i. Các tuyến xe bus được xây dựng để đảm bảo mọi cặp nút giao thông trong thành phố đều có thể liên thông với nhau thông qua một số tuyến xe trực tiếp hoặc gián tiếp. Nhà của Lam ở nút giao thông s còn trường học thì ở nút giao thông t. Do tiết kiệm chi phí, Lam đã tìm một con đường thông qua một số tuyến xe bus để di chuyển từ nhà tới trường với tổng tiền vé ít nhất. Để thuận tiện hơn, Lam đã mua vé năm cho tất cả các tuyến trên con đường đó. Các tuyến đã mua vé năm thì trong năm đó có thể đi lại mà không cần trả phí nữa. Ngoài việc thường xuyên đi lại từ nhà tới trường, Lam còn rất hay di chuyển từ thư viện ở nút giao thông u tới trung tâm Anh ngữ ở nút giao thông v. Do đó, Lam muốn lựa chọn con đường từ nhà tới trường sao cho chi phí di chuyển từ u tới v là nhỏ nhất.

Yêu cầu: Tìm chi phí nhỏ nhất để Lam di chuyển từ u tới v sau khi đã mua vé năm cho con đường từ s tới t theo như mô tả trên.

Dữ liệu: Vào từ tệp BUS.INP gồm:

Dòng đầu chứa 2 số nguyên dương n và m (n ≤10^5,m≤2.10^5 );
Dòng thứ hai chứa 2 số nguyên dương s và t (s,t≤n);
Dòng thứ ba chứa 2 số nguyên dương u và v (u,v≤n);
Dòng thứ i trong m dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương a_i,b_i,c_i mô tả tuyến xe bus thứ i (a_i,b_i≤n, c_i≤10^9; 1≤i≤m).

Kết quả: Ghi ra tệp BUS.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

    BUS.INP         BUS.OUT
    8 8             5
    1 6
    3 8
    1 2 3
    2 4 2
    2 3 3
    4 5 1
    3 5 2
    5 6 3
    2 7 4
    8 2 3
    GIẢI THÍCH
    - Đường đi từ s đến t: (1)→(2) →(4) →(5) →(6) có chi phí nhỏ nhất là 9.
    - Đường đi từ u đến v: (3)→(5) →(4) →(2) →(8) có chi phí nhỏ nhất là 5 do chỉ phải trả thêm tiền vé cho tuyến (3)→(5) và (2) →(8).

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài thoả mãn chỉ có duy nhất một con đường ngắn nhất đi từ s tới t;
• Có 50% số test ứng với 50% số điểm của bài không có ràng buộc gì thêm.