BOJ1504_특정한 최단 경로

// if (res >= INF || res < 0) cout << -1 << endl;
// 예외 조건 설정 주의
// 처음에는 if (res == INF)로 했었음

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define INF int(1e9)

using namespace std;

struct Edge {
    int to;
    int cost;
};

struct cmp {
    bool operator() (Edge a, Edge b) {
        if (a.cost >= b.cost) return false;
        else return true;
    }
};

vector<Edge> graph[801];
int d[801];
int n, e, n1, n2;

void dijkstra(int start) {
    priority_queue <Edge, vector<Edge>, cmp> pq;
    pq.push({start, 0});
    d[start] = 0;

    while (!pq.empty()) {
        Edge cur = pq.top();
        pq.pop();

        if (cur.cost > d[cur.to]) continue;

        for (int i = 0; i < graph[cur.to].size(); i++) {
            Edge next = graph[cur.to][i];
            if (d[next.to] < cur.cost + next.cost) continue;
            d[next.to] = cur.cost + next.cost;
            pq.push({next.to, d[next.to]});
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> e;
    int a, b, c;
    for (int i = 0; i < e; i++) {
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    cin >> n1 >> n2;


    for (int i = 0 ; i <= n; i++) {
        d[i] = INF;
    }

    int d1 = 0;
    int d2 = 0;
    
    dijkstra(1);

    d1 += d[n1];
    d2 += d[n2];

    for (int i = 0 ; i <= n; i++) {
        d[i] = INF;
    }

    dijkstra(n1);

    d1 += d[n2];
    d2 += d[n];

    for (int i = 0 ; i <= n; i++) {
        d[i] = INF;
    }

    dijkstra(n2);

    d1 += d[n];
    d2 += d[n1];

    // cout << d1 << " " << d2 << endl;
    int res = min(d1, d2);
    if (res >= INF || res < 0) cout << -1 << endl;
    else cout << res << endl;
}