BOJ 1504

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

#define MAXN 801
struct node{
    int cur,cnt_v1,cnt_v2,w;
    bool operator <(const node& a)const{
        return a.w < w;
    }
};
int dist[MAXN][2][2];
vector<pair<int,int> > adj[MAXN];
priority_queue<node> pq;
int N,E,v1,v2;
int dijkstra(){
    if (v1 == 1) {
        pq.push({1,1,0,0});
        dist[1][1][0] = 0;
    }
    else {
        pq.push({1,0,0,0});
        dist[1][0][0] = 0;
    }
    while (!pq.empty()){
        int cur = pq.top().cur;
        int cur_v1 = pq.top().cnt_v1;
        int cur_v2 = pq.top().cnt_v2;
        int cur_w = pq.top().w;
        pq.pop();
        if (dist[cur][cur_v1][cur_v2]!= cur_w) continue;
        for (int i = 0 ;i < adj[cur].size(); i++){
            int next = adj[cur][i].first;
            int next_w = adj[cur][i].second + cur_w;
            int next_v1 = cur_v1;
            int next_v2 = cur_v2;
            if (next == v1 && !cur_v1){
                next_v1++;
            }
            else if (next == v2 && !cur_v2){
                next_v2++;
            }
            if (dist[next][next_v1][next_v2]== -1 || dist[next][next_v1][next_v2] > next_w){
                dist[next][next_v1][next_v2] = next_w;
                pq.push({next,next_v1,next_v2,next_w});
            }
        }
    }
    return dist[N][1][1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(dist,-1,sizeof(dist));
    cin >> N >> E;
    while (E--){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    cin >> v1 >> v2;
    cout << dijkstra() <<"\n";
    return 0;
}