Informatica Online Judge

  민제 탈출기 #4 [2390 / 0956]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs17074 - ms / 1488byte
My Best Submission (C++) : N/A

[35th 이강민(gs17074)]
Writer ID : [gs17074]

Background

서현중로에서 사기를 치던 민제는 결국 감옥에 갇히게 되었다. 이 감옥은 N개의 방과 M개의 통로를 가진다.
각 통로는 방과 방을 직접 이으며, 어떤 방A와 방B가 있으면 그 사이를 잇는 통로가 여러 개일 수 있고, 방A와 방A가 연결된 통로도 있을 수 있다.
그런데, 각 통로에 설치되어 있는 보안 기계에는 고윳값이 있다. 이 고윳값의 최소값은 0, 최대값은 T이다.
민제는 K의 성능을 가지는 보안카드를 들고 이 감옥을 탈출하려 한다. 현재 민제는 1번방에 있으며, N번방이 출구이다.
민제가 보안 카드를 들고 어떤 통로를 건너면 그 고윳값이 카드에 기록된다. 카드에 기록된 값과 민제가 지날 통로의 고윳값 차이가 K를 초과하면, 간수 윤교준이 민제를 잡으러 온다.
따라서, 고윳값 차이가 K를 넘는 두 통로를 연속해서 건널 수 없다.
예를 들어, 카드의 성능이 5이고 민제가 방금 고윳값 6인 통로를 건넜으면, 다음 건널 수 있는 통로의 고윳값은 1 이상 11 이하여야 한다.
민제가 교준이에게 들키지 않고 감옥을 탈출할 수 있는 K의 최소값을 구하시오.
답은 항상 존재하며, 처음 카드에는 아무 값도 기록되어 있지 않아 아무 통로를 건너도 교준이에게 들키지 않는다.

Input

N M
s_1 e_1 t_1
...
s_m e_m t_m
첫째 줄에 방의 개수 N과 통로의 개수 M이 주어진다.
그 후 m줄 동안 통로 정보가 다음과 같이 주어진다.
s_i : i번째 통로의 시작점
e_i : i번째 통로의 끝점 (1 <= s_i, e_i <=N)
t_i : i번째 통로의 보안 기계의 고윳값 (0 <= t_i <= T)


[sub-task info]
#1 N <= 400, M <= 400, T = 1,234,567
#2 N <= 1500, M <= 1500, T = 1,234,567
#3 N <= 6000, M <= 6000, T = 1,234,567
#4 N <= 100000, M <= 200000, T = 1,000,000,000 (1e9)
#5 N <= 400000, M <= 800000, T = 1,000,000,000,000,000,000 (1e18)

Output

K
답을 한줄에 출력한다.

IO Example

입력)
3 5
1 2 4
1 2 5
1 2 6
2 3 8
2 3 9

출력)
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]