최단거리 역추적 할라고 이전문제 풀고있는데 왜 여기서 시간초과가 나냐...
다익스트라 쓴거는 지난 문제에서 쓴거랑 똑같아서 왜 시간초과나는지 전혀 모르겠어요.';



#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int dist[1001];
vector<pair<int, int>> edge[100001];

void dijkstra(int start)
{
    dist[start]=0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));

    while(!pq.empty())
    {
        int cur=pq.top().second;
        int start_to_cur_dist=-pq.top().first;
        pq.pop();
    
        for(int i=0; i<edge[cur].size(); i++)
        {
            int next=edge[cur][i].second;
            int start_to_next_dist=start_to_cur_dist+edge[cur][i].first;

            if(dist[next]>start_to_next_dist)
            {
                dist[next]=start_to_next_dist;
                pq.push(make_pair(-start_to_next_dist, next));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    
    int N, M;
    cin>>N>>M;

    for(int i=1; i<=N; i++)
        dist[i]=INF;

    for(int i=1; i<=M; i++)
    {
        int start, end, cost;
        cin>>start>>end>>cost;

        edge[start].push_back(make_pair(cost, end));
    }
    
    int S, E;
    cin>>S>>E;
    
    dijkstra(S);
    cout<<dist[E];
}