[BOJ] 최소비용 구하기2

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#define INF 987654321
#define p pair<int,int>
using namespace std;

vector<p> vc[1001];
int trace[1001];

int main(){
    int n, m;
    cin >> n >> m;
    
    memset(trace, -1, sizeof(trace));
    for(int i=0; i<m; i++){
        int from, to, val;
        scanf("%d%d%d",&from,&to,&val);
        vc[from].push_back(p(to,val));
    }
    
    int st,end;
    cin >> st >> end;
    
    int dist[1001];
    fill(dist, dist + 1001, INF);
    dist[st] = 0;
    
    priority_queue<p, vector<p>, greater<p>> pq;
    pq.push({ 0,st });
    

    // [1]
    while (! pq.empty()) {   
        int here = pq.top().second;
        int hereCost = pq.top().first;
        pq.pop();
        
        // [3]
        if(dist[here] < hereCost)
            continue;
        
        for(int i=0; i<vc[here].size(); i++){
            int next = vc[here][i].first;
            int nextCost = vc[here][i].second + hereCost;
            
            if( dist[next] > nextCost){
                dist[next] = nextCost;
                trace[next] = here;
                pq.push({ nextCost,next  });
            }
        }
    }
    
    cout << dist[end] << endl;
    int cnt = 1;
    stack<int> s;

    // [2]
    for(int i=end; i != st; i = trace[i]){   
        cnt++;
        s.push(i);
    }
    cout << cnt << endl;
    
    s.push(st);
    while (! s.empty()) {
        printf("%d ",s.top());
        s.pop();
    }
    return 0;
}