연습문제

지우는 소수를 좋아해

난이도
Lv. 4
제출
107 명
참가자
27 명
정답률
25.71 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 1초 256MB
C 1초 256MB
C++ 1초 256MB
Java 1초 256MB
Python 1초 256MB

지우는 현재 포켓몬 트레이너이다 그는 여러 체육관을 거쳐 체육관 배지를 얻은 후 마지막 포켓몬 리그에서 사천왕과 챔피언에게 도전해야 하는 임무가 주어져 있다.

각각의 체육관에는 체육관 관장들이 있고 그 관장들을 이겨야 체육관 배지를 얻을 수 있는 시스템이다. 그 관장들을 이기기 위해선 그 관장들이 갖고 있는 레벨(level)보다 높아야 한다. 하지만 너무 자주 찾아오는 지원자들 때문에 지친 체육관 관장들은 체육관 오는 길에 레벨 제한을 두었다. ‘X레벨 이하 지원자는 오지 마시오.’

지우는 포켓몬 리그를 나가기 위해 자신의 레벨을 올리면서 수련하고 있다. 수련을 하는 어느 날 지우는 자신이 포켓몬 리그에 나가기 위한 최소한의 레벨이 알고 싶어졌다. 하지만 지우는 소수(Prime Number)를 정말 좋아하기에 자신의 레벨도 소수에 맞춰서 포켓몬 리그에 참여하고 싶어 한다. 이러한 지우의 조건을 맞추어 지우에게 각각의 체육관을 넘어 마지막 장소인 포켓몬 리그에 참여할 수 있는 최소한의 레벨을 알려주는 프로그램을 작성해보자.

제약조건

2 ≤ N ≤ 10,000

1 ≤ M ≤ 100,000

1 ≤ A, B ≤ N

2 ≤ C ≤ 1,000,000,000


지우는 항상 1번 체육관에서부터 출발하고 마지막 N번 체육관을 지나가야 마지막 포켓몬 리그로 갈 수 있다. (마지막 체육관까지 가는 길은 반드시 존재한다.)

입력형식

첫 줄에는 체육관의 개수를 나타내는 정수 N과 체육관 사이의 길의 개수 정수 M이 주어진다.
둘째 줄부터는 세 정수 A, B, C가 주어진다. 이는 A번 체육관과 B번 체육관 사이에 필요 레벨이 C인 길이 존재한다는 의미이다. 서로 같은 두 체육관 사이에 여러 개의 길이 존재할 수도 있으며, 모든 길은 양방향이다.

출력형식

첫째 줄에 지우가 마지막 포켓몬 리그에 갈 수 있게 최소한의 레벨을 출력한다.

입력예제1

10 13
1 2 5
1 3 1
1 4 2
2 5 5
3 5 4
3 6 1
4 6 1
4 7 3
5 8 5
6 9 4
7 9 2
8 10 5
9 10 3
출력예제1

5

입력예제2

9 12
4 6 24
3 2 2
1 4 8
4 3 8
4 3 16
3 5 6
2 6 29
1 5 30
7 9 28
1 8 10
7 6 16
8 5 16
출력예제2

29

목록