3번 4번 히든 케이스에서 자꾸 시간초과가 발생하는데 뭐가 문제인지 모르겠어요 ㅠㅠ

/*
지우는 소수를 좋아해
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

다익스트라 우선순위 큐로 구현
하지만, 거리에 상관없이 레벨만 낮으면 오케이

1번에서 시작해서 n번으로 가는 길 찾고,
최소 레벨을 구한다.
그 최소레벨보다 높은 소수 구한다.

지우는 항상 1번 체육관에서부터 출발하고 
마지막 N번 체육관을 지나가야 마지막 포켓몬 리그로 갈 수 있다. (마지막 체육관까지 가는 길은 반드시 존재한다.)
*/
#include <iostream>
#include <queue>
#include <algorithm>
#include <math.h>
#define INF 1e9
#define MAX 1000000000
using namespace std;

//globals
int N,M;
vector<pair<int,int>> graph[10001];
int d[10001];

//methods
void Input(){
    cin>>N>>M;
    
    for(int i=0; i<M; i++){
        int a,b,c;
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
}

int dijkstra(int start){
    
    fill(d,d+N+1,INF);
    priority_queue<pair<int,int>> pq;
    pq.push({0,start});
    d[1]=0;
    while(!pq.empty()){
        int current_node=pq.top().second;
        int current_level=pq.top().first;
        pq.pop();
        for(int i=0; i<graph[current_node].size(); i++){
            int next_level=max(current_level, graph[current_node][i].second);
            int next_node=graph[current_node][i].first;
            if(next_level<d[next_node]){
                d[next_node]=next_level;
                pq.push({next_level,next_node});
            }
        }
    }
    return d[N-1];
}
int check_prime(int num){
    for(int i=d[N]+1;;i++){
        bool isFind=true;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0) {
                isFind=false;
                break;
            }
        }
        if(isFind) {
            return i;
        }
        
        
    }
    return -1;
}
void Start(){
    //1번에서 N번까지 가는 최소 레벨 구하기
    //dfs(1,0);
    int tmp=dijkstra(1);
    //cout<<d[N]<<'\n';
    //구간합을 이용하여, minn바로 뒤의 소수 구하기
    int result=check_prime(tmp);
    cout<<result<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Start();
    return 0;
}