9도 1545 이상한 연결도(최단 경로 변형)

제목.
최소 정수 k를 구하는 무방향 대역 그래프를 알고 있습니다.k보다 작은 값만 사용할 수 있도록 노드 1은 노드 n과 연결할 수 있습니다
 
사고의 방향
1.이것은 가장 짧은 경로의 변형 문제일 것이다
2. 클래식 dijkstra의 거리 계산 공식을 조금 변형시키면 된다
3. 이 문제는 BFS도 할 수 있을 것 같다
4. 다음 코드가 시간이 초과되어 마지막 사례를 계산하지 못했습니다. 저는 Edge를 모두 Edge*로 바꾸려고 했지만 더 느릴 줄은 몰랐습니다.
 
코드가 9도 테스트를 통과하지 못했습니다

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

class Edge {
public:
    Edge(int _ed, int _wt):ed(_ed), weight(_wt){}
    Edge() {
        Edge(0,0);
    }
    int ed, weight;

    bool operator<(const Edge &ths) const {
        return this->weight > ths.weight;
    }
};

vector<Edge> graph[10010];
int dis[10010];


int dijkstra(int n) {
    priority_queue<int> heap;
    heap.push(1);
    dis[1] = 0;

    while(!heap.empty()) {
        int father = heap.top();
        heap.pop();
        if(father == n)
            continue;

        for(int i = 0; i < graph[father].size(); i ++) {
            int j = graph[father][i].ed;

            if(max(dis[father],graph[father][i].weight) < dis[j]) {
                dis[j] = max(dis[father],graph[father][i].weight);
                heap.push(j);
            }
        }
    }

    if(dis[n] == 0X3F3F3F3F)
        return -1;
    return dis[n];
}

int main() {
    freopen("testcase.txt", "r", stdin);
    int nodes, edges;
    while(scanf("%d%d", &nodes, &edges) != EOF) {
        int st, ed, wt;
        for(int i = 1; i <= nodes; i ++) {
            graph[i].clear();
            dis[i] = 0X3F3F3F3F;
        }

        for(int i = 0; i < edges; i ++) {
            scanf("%d%d%d", &st, &ed, &wt);
            graph[st].push_back(Edge(ed, wt));
            graph[ed].push_back(Edge(st, wt));
        }

        int res = dijkstra(nodes);
        printf("%d
", res);
    }
    return 0;
}