問題文

雪男君と雪女さんはyuki国に旅行に来ました。yuki国は $1, 2, \ldots , N$ の番号がついた $N$ 個の街と、$1, 2, \ldots, M$ の番号がついた $M$ 本の道からなります。道 $i$ ($1\leq i\leq M$) は街 $a_i$ と街 $b_i$ を双方向に結んでいます。$2$ 人の歩く速さは同じであり、道 $i$ を歩くのにかかる時間は $2$ 人とも $c_i$ 分です。ただし、道を途中で引き返すことはできません。

$2$ 人ははじめ空港のある街 $1$ にいて、街 $P$ と街 $Q$ にある観光名所に歩いて行こうと思っていましたが、$T$ 分後には街 $1$ に戻っていなくてはならないことに気づきました。そこで $2$ 人は次を満たすように行動することにしました。

• $2$ 人のうち少なくとも一方が街 $P$ を訪れる。
• $2$ 人のうち少なくとも一方が街 $Q$ を訪れる。

しかし $2$ 人はとても仲良しなので、できるだけ $2$ 人で一緒に行動する時間を長くしたいです。$T$ 分間のうち $2$ 人一緒に行動できる時間の最大値を求めてください。

ただし、$2$ 人で同じ場所で待機している時間も一緒に行動する時間に含まれます。

入力

$N\ M\ P\ Q\ T$
$a_1\ b_1\ c_1$
$\ldots$
$a_M\ b_M\ c_M$

• $3\leq N\leq 2000$
• $2\leq M\leq 10^5$
• $2\leq P < Q\leq N$
• $1\leq T\leq 10^9$
• $1\leq a_i < b_i\leq N$
• $1\leq c_i\leq 10^9$
• $i\neq j$ のとき $(a_i, b_i)\neq (a_j, b_j)$
• 街 $1$ からすべての街に歩いて行くことができる。
• 入力はすべて整数である。

出力

問題文の条件を満たしつつ $2$ 人一緒に行動できる時間の最大値を分単位で出力せよ。ただしどのように行動しても条件を満たすことができない場合は $-1$ を出力せよ。

サンプル

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

7

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

20

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

-1

5 5 2 5 12
2 4 1
3 5 5
1 3 1
2 5 10
1 4 1

2