Điểm hẹn

Một thành phố có $n$ nút giao thông đánh số từ $1$ đến $n$ và $m$ con đường hai chiều. Con đường thứ $i$ nối hai nút $u_i$, $v_i$ và có độ dài $w_i$. Có thể có đường nối một nút với chính nó và nhiều đường nối cùng một cặp nút.

An đang ở nút $a$, Bình đang ở nút $b$. Lúc $0$ cả hai cùng xuất phát, mỗi người đi với vận tốc $1$ (đi hết con đường độ dài $w$ mất $w$ đơn vị thời gian) và được phép đứng chờ tại một nút. Hai bạn muốn hẹn gặp nhau tại một nút $v$ nào đó. Thời điểm sớm nhất cả hai cùng có mặt tại $v$ là $max(d_a(v),d_b(v))$, trong đó $d_a(v)$, $d_b(v)$ là độ dài đường đi ngắn nhất từ $a$ và từ $b$ tới $v$.

Hãy chọn nút hẹn sao cho thời điểm gặp nhau là sớm nhất. Nếu có nhiều nút cho cùng thời điểm sớm nhất, chọn nút có số thứ tự nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên $n$, $m$, $a$, $b$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$.

Dữ liệu ra

Nếu không có nút nào cả hai bạn cùng tới được, in ra $-1$. Ngược lại in ra hai số: thời điểm gặp nhau sớm nhất và nút hẹn.

Ràng buộc

• $1\le n\le 3·{10}^4$
• $0\le m\le 6·{10}^4$
• $1\le a,b,u_i,v_i\le n$
• $1\le w_i\le {10}^9$

Ví dụ