说明

时间限制：1 Sec 内存限制：256 MB 输入文件：friend.in 输出文件：friend.out

小明和小红来到 A 国旅行。A 国有编号 $1,2,\dots,N$ 的 $N$ 座城市，以及 $M$ 条双向道路。第 $i$ 条道路双向连接城市 $a_i$、$b_i$；两人步行速度完全相同，走道路 $i$ 都需要花费 $c_i$ 分钟。不允许走到道路中途折返。

两人一开始都在有机场的城市 $1$，原本打算步行去城市 $P$、$Q$ 的景点，但是发现必须在 $T$ 分钟时回到城市 $1$。于是他们约定行动满足两条硬性条件：

1、两人里至少有一人到访过城市 $P$；

2、两人里至少有一人到访过城市 $Q$。

两人关系很好，希望全程里共同在一起行动的总时间尽可能长。请求出两人共处时间的最大值。

补充规则：两人待在同一个地点原地等待的时间，也算在一起行动的时间。

输入格式

第一行五个整数 $N,M,P,Q,T$。

接下来 $M$ 行，每行三个整数 $a_i,b_i,c_i$。

输出格式

输出满足所有条件下，两人共处时间的最大分钟数；

如果无论如何行动都无法满足两条景点访问要求，输出 $-1$。

样例

样例 1

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

7

样例说明：

可行行动方案：

1. 小明路线：$1→3→2→3$，在 $3$ 等待 $2$ 分钟，再返回 $1$，最后在 $1$ 等待 $3$ 分钟。

2. 小红路线：$1→3→4→3→1$，在 $1$ 等待 $3$ 分钟。

共处时间段：$0 \sim 2$ 分钟、$10 \sim 15$ 分钟，合计 $7$ 分钟。

说明：可以提前回到城市 $1$，提前回来后到 $T$ 时刻为止在 $1$ 等待的时间全部计入共处时长。

样例 2

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

20

样例说明：

两人全程同步走同一条路线：$1→3→2→3→4→3→1$，回到 $1$ 之后原地等待 $2$ 分钟，全程 $20$ 分钟都在一起。

样例 3

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

-1

样例说明：

不存在任何行动方案能同时满足至少一人去 $P$、至少一人去 $Q$，无解。

样例 4

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

2

数据范围

对于 4% 的数据，$N,M,T,c_i \le 10$。

对于 20% 的数据，$N,M,T,c_i \le 100$。

对于 32% 的数据，$N,M,T,c_i \le 1000$。

对于 60% 的数据，$T,c_i \le 10^6$。

另有 8% 的数据，$N,M \le 100$。

对于 100% 的数据，$3 \le N \le 2000$，$2 \le M \le 10^5$，$1 \le T \le 10^9$，$1 \le c_i \le 10^9$，任意两条道路的端点对互不相同，城市 $1$ 可以到达所有其他城市。

对于 100% 的数据，$2 \le P \lt Q \le N$，$1 \le a_i \lt b_i \le N$，任意两条道路的端点对互不相同，城市 $1$ 可以到达所有其他城市。