题目描述

给定一个 $n$ 个节点，$m$ 条有权边的有向图，第 $i$ 条边的边权是 $w_i$，从 $u_i$ 到 $v_i$， Reimu 从 $s$ 点出发，目标是到 $t$ 点找 Satori。

Reimu 想尽快到达 $t$ 点，所以她让 Yukari Yakumo 帮助她，有一个技能是可以对任意两个点 $x,y$，新建一条 $x$ 到 $y$ 的边，边权为 $(x-y)^2$，这个技能只能使用一次。

求 $s$ 到 $t$ 的最小时间？

输入格式

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

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

输出格式

一行一个数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

6

提示

Reimu 可以从 $1$ 走到 $2$，然后从 $2$ 走到 $3$，用时为 $3+1=4$，然后用技能建立 $3,4$ 之间的边，代价为 $(3-4)^2=1$，于是走到 $4$ 用时为 $4+1=5$，然后走到 $5$ 用时为 $5+1=6$。

数据范围

本题采用子任务评测。

对于 $20\%$ 的数据，满足 $1\leq n\leq 5$ 且 $1\leq m\leq 10$。

对于 $40\%$ 的数据，满足 $1\leq n\leq 100$ 且 $1\leq m\leq 300$。

对于 $60\%$ 的数据，满足 $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$。