/*
* Problem :: 1504 / 특정한 최단 경로
*
* Kind :: Dijkstra
*
* Insight
* - 경로 1: 1 -> v1 -> v2 -> N
* 경로 2: 1 -> v2 -> v1 -> N
* 이 두 경로중 무엇이 더 빠른가 하는 문제다
* + max(N)=800, max(E)=2*10^5 이니
* O(|E|log|E|) 시간복잡도의 다익스트라 알고리즘이라면
* 6번 정도 돌려도 시간 제한내에 통과할 수 있을 것 같다
*
* Point
* - 플로이드-워셜 알고리즘으로도 풀리긴 한다
*
* - 최단거리의 최대거리는 max(c)=1000 * max(N-1)=799 이므로
* 799 * 1000 보다 큰 최단거리는 불가능하다
* + 그래서 INF 를 (800*1000+1) 로 설정했다
* # 경로 1에서 (1 -> v1) 은 10 인데 (v1 -> v2) 가 INF 가 나왔다면
* 경로 1은 불가능한 경우이고, 거리는 INF 보다 커지게 된다
* -> 최악의 경우는 각 경로의 길이가 INF + INF + INF 가 되는 것인데
* Overflow 는 일어나지 않는다 (휴)
* => 즉, 각 경로가 불가능하다면 경로의 길이가 INF 이상이 된다
* 이를 통해 가능여부를 판단해주자
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N, E;
struct Node { int no, dist; };
struct State { int no, dist; };
vector<Node> A[800+1];
#define INF (800*1000+1)
// Set up : Functions Declaration
bool operator > (State &u, State &v);
int Dijkstra(int s, int e);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N >> E;
for (int i=0; i<E; i++) {
int a, b, c;
cin >> a >> b >> c;
A[a].push_back({b, c});
A[b].push_back({a, c});
}
int v1, v2;
cin >> v1 >> v2;
// Process
int tmp1 = Dijkstra(1, v1) + Dijkstra(v1, v2) + Dijkstra(v2, N);
int tmp2 = Dijkstra(1, v2) + Dijkstra(v2, v1) + Dijkstra(v1, N);
int ans = min(tmp1, tmp2);
// Control : Output
cout << ((ans >= INF) ? -1 : ans) << endl;
}
// Helper Functions
bool operator > (State &u, State &v)
/* 구조체 State 비교를 위한 연산자 오버로딩 */
{
return make_tuple(u.dist, u.no) > make_tuple(v.dist, v.no);
}
int Dijkstra(int s, int e)
/* 다익스트라 알고리즘을 활용하여
* 정점 s 부터 정점 e 까지의 최단거리를 반환 */
{
int dp[N+1];
fill(&dp[1], &dp[N+1], INF);
priority_queue<State,vector<State>,greater<>> pq;
dp[s] = 0;
pq.push({s, dp[s]});
while (not(pq.empty())) {
auto [c, cd] = pq.top();
pq.pop();
if (cd > dp[c]) continue;
for (auto [n, d] : A[c]) {
/* Relaxation */
if (dp[n] > dp[c]+d) {
dp[n] = dp[c]+d;
pq.push({n, dp[n]});
}
}
}
return dp[e];
}