The JAG Kingdom consists of $N$ cities and $M$ bidirectional roads. The $i$-th road ($u_i, v_i, c_i$) connects the city $u_i$ and the city $v_i$ with the length $c_i$. One day, you, a citizen of the JAG Kingdom, decided to go to the city $T$ from the city $S$. However, you know that one of the roads in the JAG Kingdom is currently under construction and you cannot pass the road. You don't know which road it is. You can know whether a road is under construction only when you are in either city connected by the road.

Your task is to minimize the total length of the route in the worst case. You don't need to decide a route in advance of departure and you can choose where to go next at any time. If you cannot reach the city $T$ in the worst case, output '-1'.



Input

The input consists of a single test case formatted as follows.


$N$ $M$ $S$ $T$
$u_1$ $v_1$ $c_1$
:
$u_M$ $v_M$ $c_M$


The first line contains four integers $N, M, S,$ and $T$, where $N$ is the number of the cities ($2 \leq N \leq 100,000$), $M$ is the number of the bidirectional roads ($1 \leq M \leq 200,000$), $S$ is the city you start from ($1 \leq S \leq N$), and $T$ is the city you want to reach to ($1 \leq T \leq N, S \ne T$). The following $M$ lines represent road information: the $i$-th line of the $M$ lines consists of three integers $u_i, v_i, c_i,$ which means the $i$-th road connects the cities $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N, u_i \ne v_i$) with the length $c_i$ ($1 \leq c_i \leq 10^9$). You can assume that all the pairs of the cities are connected if no road is under construction. That is, there is at least one route from city $x$ to city $y$ with given roads, for all cities $x$ and $y$. It is also guaranteed that there are no multiple-edges, i.e., $\\{u_i,v_i\\} \ne \\{u_j,v_j\\}$ for all $1 \leq i < j \leq M$.

Output

Output the minimum total length of the route in the worst case. If you cannot reach the city $T$ in the worst case, output '-1'.

Examples

Input

3 3 1 3
1 2 1
2 3 5
1 3 3


Output

6


Input

4 4 1 4
1 2 1
2 4 1
1 3 1
3 4 1


Output

4


Input

5 4 4 1
1 2 3
2 3 4
3 4 5
4 5 6


Output

-1
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define maxn 100010
#define maxm 800010
typedef long long ll;
struct Edge {
	Edge *next;
	int to, w;
} *last[maxn], e[maxm], *ecnt = e;
inline void link(int a, int b, int w)
{
	*++ecnt = (Edge) {last[a], b, w}; last[a] = ecnt;
	*++ecnt = (Edge) {last[b], a, w}; last[b] = ecnt;
}
ll d[maxn];
int fa[maxn];
int n, m, s, t;
ll f[maxn];
struct Node *null;
struct Node {
	Node *ch[2];
	ll val, tag;
	int lca;
	inline void set_tag(ll tg)
	{
		val += tg;
		tag += tg;
	}
	inline void pushdown()
	{
		if (tag)
		{
			if (ch[0] != null) ch[0] -> set_tag(tag);
			if (ch[1] != null) ch[1] -> set_tag(tag);
			tag = 0;
		}
	}
} *root[maxn], mem[maxm], *tot = mem;
Node *merge(Node *a, Node *b)
{
	if (a == mem) return b;
	if (b == mem) return a;
	if (a -> val > b -> val) std::swap(a, b);
	a -> pushdown();
	std::swap(a -> ch[0], a -> ch[1]);
	a -> ch[1] = merge(a -> ch[1], b);
	return a;
}
int son[maxn], size[maxn], top[maxn], dep[maxn], inv[maxn], dfn[maxn], timer;
void dfs1(int x)
{
	size[x] = 1; dep[x] = dep[fa[x]] + 1;
	for (Edge *iter = last[x]; iter; iter = iter -> next)
		if (fa[iter -> to] == x)
		{
			dfs1(iter -> to);
			size[x] += size[iter -> to];
			size[iter -> to] > size[son[x]] ? son[x] = iter -> to : 0;
		}
}
void dfs2(int x)
{
	top[x] = son[fa[x]] == x ? top[fa[x]] : x;
	dfn[x] = ++timer;
	for (Edge *iter = last[x]; iter; iter = iter -> next)
		if (fa[iter -> to] == x) dfs2(iter -> to);
	inv[x] = timer;
}
inline int getlca(int a, int b)
{
	while (top[a] != top[b])
		dep[top[a]] < dep[top[b]]
			? b = fa[top[b]]
			: a = fa[top[a]];
	return dep[a] < dep[b] ? a : b;
}
void dfs(int x)
{
	root[x] = mem;
	for (Edge *iter = last[x]; iter; iter = iter -> next)
		if (fa[iter -> to] == x)
		{
			dfs(iter -> to);
			if (root[iter -> to] != null) root[iter -> to] -> set_tag(iter -> w);
			root[x] = merge(root[x], root[iter -> to]);
		}
		else if (iter -> to != fa[x])
		{
			*++tot = (Node) {{mem, mem}, d[iter -> to] + iter -> w, 0, getlca(x, iter -> to)};
			root[x] = merge(root[x], tot);
		}
	while (root[x] != null && dfn[x] <= dfn[root[x] -> lca] && dfn[root[x] -> lca] <= inv[x])
		root[x] = merge(root[x] -> ch[0], root[x] -> ch[1]);
	f[x] = root[x] -> val;
}
struct Queue {
	ll d; int x;
	inline bool operator < (const Queue &that) const {return d > that.d;}
} ;
std::priority_queue<Queue> q;
inline bool check(ll mid)
{
	 memset(d, 63, sizeof (d));
	 const ll inf = d[0];
	 q.push((Queue) {d[s] = 0, s});
	 while (!q.empty())
	 {
	 	Queue now = q.top(); q.pop();
	 	if (now.d != d[now.x]) continue;
	 	int x = now.x;
	 	if (d[x] + f[x] > mid) continue;
	 	for (Edge *iter = last[x]; iter; iter = iter -> next)
	 		if (d[iter -> to] > d[x] + iter -> w)
	 		{
	 			d[iter -> to] = d[x] + iter -> w;
	 			q.push((Queue) {d[iter -> to], iter -> to});
	 		}
	 }
	 return d[t] != inf;
}
int main()
{
	null = mem; mem -> val = ~0ULL >> 3; mem -> ch[0] = mem -> ch[1] = mem;
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 1; i <= m; ++i)
	{
		int a, b, w; scanf("%d%d%d", &a, &b, &w);
		link(a, b, w);
	}
	memset(d, 63, sizeof (d));
	q.push((Queue) {d[t] = 0, t});
	while (!q.empty())
	{
		Queue now = q.top(); q.pop();
		if (now.d != d[now.x]) continue;
		int x = now.x;
		for (Edge *iter = last[x]; iter; iter = iter -> next)
			if (d[iter -> to] > d[x] + iter -> w)
			{
				d[iter -> to] = d[x] + iter -> w;
				q.push((Queue) {d[iter -> to], iter -> to});
			}
	}

	for (int i = 1; i <= n; ++i)
		for (Edge *iter = last[i]; iter; iter = iter -> next)
			if (d[iter -> to] == d[i] + iter -> w)
				fa[iter -> to] = i;

	dfs1(t);
	dfs2(t);
	dfs(t);
//	for (int i = 1; i <= n; ++i) printf("%lld\n", f[i]);
	ll left = 0, right = 1e18;
	while (left < right)
	{
		ll mid = left + right >> 1;
		if (check(mid)) right = mid;
		else left = mid + 1;
	}
	printf("%lld\n", left > 1e17 ? -1 : left);
	return 0;
}
