You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目信息

时间限制: 1.5s

空间限制: 512M

输入文件: far.in

输出文件: far.out

题目描述

Earth 宇宙的 president BD 听说有人润去 B 宇宙后大发雷霆！于是雇用了臭名昭著的雇佣军 C 舰队要讨个说法！根据 BD 提供的地图，C 舰队需要从第 $s$ 个星球出发，抵达第 $t$ 个星球以靠近跨越宇宙的白金虫洞。

星际航行充满了未知危险，所以星球间的通道都是单向修建的，BD 提供的地图包括了 $n$ 个星球和 $m$ 条星球通道，第 $i$ 条通道指示了从第 $u_i$ 个星球到第 $v_i$ 星球需要消耗 $w_i$ 单位的燃料。

C 舰队臭名昭著的原因之一是其在每次远征中都会携带一块后备隐藏能源，只要启动后备隐藏能源就能任意修建一条 $x$ 星到 $y$ 星的临时通道，而后可以消耗 $(x-y)^2$ 单位燃料通过。注意总共只能修建一次，

C 舰队的舰长 u 想知道 C 舰队最少需要消耗多少单位燃料才能从 $s$ 星抵达 $t$ 星。

输入格式

第一行四个数表示 $n,m,s,t$。

之后 $m$ 行，每行三个数 $u,v,w$ 表示原有的一条边，保证无重边。

输出格式

输出一行一个整数表示答案。

5 6 1 5
1 2 3
1 3 5
2 3 1
3 4 10
4 5 1
3 5 8

6

大样例

cc.in
cc.out

样例解释

C 舰队可以从 $1$ 星到 $2$星，然后从 $2$ 星到 $3$星，消耗燃料为 $3+1=4$，然后用后备隐藏能源建立 $3$ 星到 $4$ 星的边，代价为 $(3-4)^2=1$，于是到 $4$ 星消耗燃料为 $4+1=5$，最后到 $5$ 星消耗燃料 $5+1=6$。

数据范围与提示

• 对于 $30\%$ 的数据，满足 $1\leq n\leq 5$ 且 $1\leq m\leq 10$。
• 对于 $45\%$ 的数据，满足 $1\leq n\leq 100$ 且 $1\leq m\leq 300$。
• 对于 $55\%$ 的数据，满足 $1\leq n\leq 2000$ 且 $1\leq m\leq 10000$。
• 对于 $100\%$ 的数据，满足 $1\leq s, t\leq n\leq 2\times 10^5$, $0\leq m\leq 4\times 10^5$，$1\leq w\leq 10^9$。