// 1 - > a - > b ->목적지
1 - > b - > a ->목적지
이 개념을 생각해서 풀면된다.
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 300000000
using namespace std;
int N, E; //정점의 개수<=800, 간선의 개수<=200,000
vector <vector <pair<int, int> > > mat(20017);
vector<int> dijkstra(int s){
priority_queue <pair<int,int>, vector <pair<int,int> >, greater<pair <int,int> > > pq; //가려는 점까지 드는 비용,가려는 점
pq.push(make_pair(0,s)); //처음 비용, 현재 위치한 점
vector <int> dist(N+1, INF);
dist[s]=0;
while(!pq.empty()){
int cost = pq.top().first;
int here = pq.top().second;
pq.pop();
if(dist[here]<cost) continue;
for(int i=0;i<mat[here].size();i++){
int nextcost= cost + mat[here][i].second;
int there=mat[here][i].first;
if(dist[there]>nextcost){
dist[there]=nextcost;
pq.push(make_pair(nextcost,there));
}
}
}
return dist;
}
int main(){
scanf("%d %d",&N,&E);
for(int i=0;i<E;i++){
int a, b, c; //a부터 b까지 양방향 길, 거리 c
scanf("%d %d %d",&a,&b,&c);
mat[a].push_back(make_pair(b,c)); //방향성 a->b
mat[b].push_back(make_pair(a,c)); //방향성 b->a
}
int h, y; //거쳐야 하는 점
scanf("%d %d", &h, &y);
vector <int> s2h;
vector <int> h2y;
vector <int> y2N;
s2h=dijkstra(1); //h
h2y=dijkstra(h); //y
y2N=dijkstra(y); //N
int hy=s2h[h]+h2y[y]+y2N[N]; //시작점에서 h로 최단거리, h를 기준으로 y까지 최단거리 , y를 기준으로 N까지 최단거리
int yh=s2h[y]+y2N[h]+h2y[N]; //시작점에서 y로 최단거리, y를 기준으로 h까지 최단거리 , h를 기준으로 N까지 최단거리
int res = min(hy, yh);
if(res>=INF){
printf("-1\n");
}
else{
printf("%d\n", res);
}
return 0;
}
