군사 이동

전쟁 당시 북부 왕국의 국왕은 남부 왕국을 공격하는 작전을 세운 적이 있다. 두 나라의 영토는 p개의 지점과 w개의 길로 나타낸다. 모든 길은 양방향이고, 길마다 너비가 정해져 있어 그 너비에 비례하는 수의 군사가 지나갈 수 있다.

국왕은 군사가 뭉쳐 움직이는 편이 유리하다고 보고, 남부 왕국으로 가는 경로를 미리 하나 정한 다음 모든 군사를 그 경로로만 보냈다. 국왕은 총명해서 경로에 놓인 길 가운데 가장 좁은 길의 너비가 최대가 되는 경로를 골랐다.

전쟁 통에 어느 경로로 보냈는지 적어 둔 기록이 불타 없어졌다. 전쟁사를 마무리하려면 이 기록이 필요하다. 위대한 과학자인 당신이 복구해 달라.

첫 줄에 지점의 수 p와 길의 수 w가 공백을 사이에 두고 주어진다. ($2 \le p \le 1000$, $1 \le w \le 50000$)

둘째 줄에 북부 왕국의 수도 c와 남부 왕국의 수도 v가 공백을 사이에 두고 주어진다. ($0 \le c, v < p$, $c \ne v$)

다음 w개 줄에 길이 잇는 두 지점 wstart와 wend, 그리고 그 길의 너비 wwidth가 공백을 사이에 두고 주어진다. ($0 \le wstart, wend < p$, $wstart \ne wend$, $1 \le wwidth \le 1000$)

같은 두 지점을 잇는 길이 여러 개 주어질 수 있다. c에서 v로 가는 경로는 적어도 하나 있다.

국왕이 정한 경로에 놓인 길 가운데 가장 좁은 길의 너비를 첫 줄에 출력한다.