소프티어

다익스트라를 이용한 풀이가 정해라는 것은 알고 있습니다만
parametric search + bfs 로도 해결이 가능할 것 같아서 시도해 보았는데

5~6개의 케이스가 자꾸 통과가 안되네요..

예외 케이스 좀 받아볼 수 있을까요?

#include 
#include 
#include 
#include 
using namespace std;

#define MAXN 1000000001
queue q;
vector> v[10001];

bool bfs(int start, int end, int level) {
	bool vi[10001];
	fill(vi, vi + 10001, false);

	q.push(start);
	vi[start] = true;

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		if (now == end) return true;
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i].second;
			int req_level = v[now][i].first;

			if (level > req_level && !vi[next]) {
				q.push(next);
				vi[next] = true;
			}
		}
	}

	return false;
}

bool isPrime(int num) {
	for (int i = 2; i * i <= num; i++) {
		if (num % i == 0) return false;
	}
	return true;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		v[a].push_back({ c,b });
		v[b].push_back({ c,a });
	}

	int l = 0, r = MAXN;

	while (l + 1 != r) {
		int mid = (l + r) / 2;
		bool res = bfs(1, n, mid);

		if (res) {
			r = mid;
		}//마지막 체육관 도달
		else {
			l = mid;
		}//체육관 도달 못함
	}

	for (int i = r;; i++) {
		if (isPrime(i)) {
			cout << i;
			break;
		}
	}


}