거의 최단 경로

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <functional>
#define MAXX 501 
#define INF 987654321
using namespace std;
 
typedef pair<int, int> pp;
vector<pp> edges[MAXX];
int cost[MAXX];
bool visited[MAXX];
 
void backDijkstra(int start, int len, int n) {
    priority_queue<pp, vector<pp>, greater<pp> > pq;
    pq.push(pp(len, start));
 
    cost[start] = len;
 
    //거꾸로 시작 
    while (!pq.empty()) {
        int c_cost = pq.top().first;
        int now = pq.top().second;
        pq.pop();
 
        if (visited[now]) continue;
        visited[now] = true;
 
        //now로 들어오는 간선
        for (int i = 0; i < n; i++) {
            vector<pp> tmp;
            for (auto edge : edges[i]) {
                if (edge.second == now) {
                    //들어오는 간선이 지금 노드일 때 
                    if (c_cost - edge.first == cost[i]) {
                        //최단 경로에 포함된 간선이다. 
                        //간선을 없애버린다. 
 
                        pq.push(pp(c_cost - edge.first, i));
                        continue;
                    }
                    
                }
                tmp.push_back(edge);
            }
            edges[i] = tmp;
        }
    }
 
}
void dijkstra(int start, int dest) {
    priority_queue<pp, vector<pp>, greater<pp> > pq;
 
    pq.push(pp(0, start));
 
    cost[start] = 0;
 
    while (!pq.empty()) {
        int c_cost = pq.top().first;
        int now = pq.top().second;
        pq.pop();
 
        if (visited[now]) continue;
        visited[now] = true;
 
        for (auto i : edges[now]) {
            int next = i.second;
            int n_cost = i.first;
 
            if (!visited[next] && cost[next] > cost[now] + n_cost) {
                cost[next] = cost[now] + n_cost;
                pq.push(pp(cost[next], next));
            }
        }
 
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    //거의최소 경로는 시작 점에서 나가는 경로가 하나일 경우에는 있을 수 없다. 
    while (1) {
        int n, m, s, d;
        cin >> n >> m;
 
        if (!n && !m) break;
 
        for (int i = 0; i < n; i++) edges[i].clear();
        memset(visited, 0, sizeof(visited));
 
        cin >> s >> d;
 
        for (int i = 0; i < n; i++) cost[i] = INF;
 
        int cntIn = 0;
        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
 
            edges[a].push_back(pp(c, b));
            if (b == d) {
                cntIn++;
                
            }
        }
        //방향 그래프 
        if (cntIn == 1) {
            cout << -1 << '\n';
            continue;
        }
 
        dijkstra(s, d);
 
        //거꾸로 돌리면서 최단 경로에 포함되는 간선을 제외시킨다. 
        memset(visited, 0, sizeof(visited));
 
        backDijkstra(d, cost[d], n);
 
 
        for (int i = 0; i < n; i++) cost[i] = INF;
 
        memset(visited, 0, sizeof(visited));
 
        dijkstra(s, d);
 
        
        if (cost[d] == INF) cout << -1 << '\n';
        else cout << cost[d] << '\n';
        
    }
 
    return 0;
}