군사 이동

면접 대비

시간 제한2초메모리 제한256 MB

요약
두 도시를 잇는 경로 가운데 가장 좁은 도로가 가장 넓은 경로를 찾아 그 너비를 출력합니다.
난이도

보통10점 중 4점

유형
최소 신장 트리, 유니온 파인드, 정렬
정답자
아직 제출이 없습니다

문제

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

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

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

입력

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

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

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

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

출력

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

예제6

  1. 예제 1

    입력
    7 11
3 5
0 1 15
0 2 23
1 2 16
1 3 27
2 4 3
2 6 21
3 4 14
3 5 10
4 5 50
4 6 9
5 6 42
    예상 출력
    16

  2. 예제 2

    입력
    2 1
0 1
0 1 1
    예상 출력
    1

  3. 예제 3

    입력
    2 3
1 0
0 1 7
0 1 1000
1 0 4
    예상 출력
    1000

  4. 예제 4

    입력
    5 4
0 4
0 1 100
1 2 5
2 3 100
3 4 100
    예상 출력
    5

  5. 예제 5

    입력
    6 7
0 5
0 1 9
1 5 9
0 2 8
2 3 8
3 4 8
4 5 8
1 3 2
    예상 출력
    9

  6. 예제 6

    입력
    6 6
0 5
0 5 3
0 1 6
1 2 6
2 3 6
3 4 6
4 5 6
    예상 출력
    6