### 问题描述 小蓝作为异世界最大流媒体网站 `LanTube` 的高级算法工程师，他想要实现更加精准的视频推荐服务，来满足用户的喜好。其中，“视频的相关性”是一个重要指标，它代表了两个视频 $A$ 到 $B$ 的关联程度，记作 $f(A,B)$。 现在我们给出两个视频 `相关性` 的定义：若 $A$ 视频，在通过一系列相关联视频构成的路径中，可以关联到 $B$ 视频，则称此条路径为 `相关路径`，而相关性 $f(A,B)$ 等于**每一条**相关路径上最小相关性的总和。 例如：视频 $A$ 与视频 $B,C$ 相关，相关性 $f(A,B) = 10, f(A,C)=2$；视频 $B$ 与视频 $D$ 相关，$f(B,D) = 5$；视频 $C$ 与视频 $D$ 相关，$f(C,D) = 3$。则在相关路径 $A\rightarrow B\rightarrow D$ 中，最小相关性为 $5$，在相关路径 $A\rightarrow C\rightarrow D$ 中，最小相关性为 $3$，则 $f(A,D) = 5+3=8$。 现在给出了 $N$ 部视频，序号依次为 $1 \sim N$。并已知 $M$ 条关于第 $a$ 部视频到第 $b$ 部视频相关性 $f(a,b)$，其中 $a \neq b$。 求第 $S$ 部视频到第 $T$ 部视频的相关性。 ### 输入格式 第一行包含四个正整数 $N,M,S,T$，代表有 $N$ 个视频，有 $M$ 对视频的相关性，求第 $S$ 和第 $T$ 部视频相关性。 接着下面 $M$ 行，每行有三个整数 $a,b,f(a,b)$，代表第 $a$ 部到第 $b$ 部视频相关性为 $f(a,b)$。 ### 输出格式 输出一个正整数，代表第 $S$ 和第 $T$ 部视频相关性。 ### 输入样例 ```txt 7 8 2 7 2 1 50 2 3 40 1 4 40 3 4 50 4 5 20 4 6 40 5 7 30 6 7 40 ``` ### 输出样例 ```txt 60 ``` ### 说明 题目中存在两条相关路径： - $2\rightarrow 1\rightarrow 4\rightarrow 5\rightarrow 7$，该路径中最小相关性为 $20$。 - $2\rightarrow 3\rightarrow 4\rightarrow 6\rightarrow 7$，该路径中最小相关性为 $40$。 综上，第 $2$ 部到第 $7$ 部的相关性为 $60$。 ### 数据范围 对于所有数据，保证 $2\leq N \leq 100$，$1\leq M \leq 1000$，$1\leq S \neq T\leq N$， $1\leq a,b\leq N$，$f(a,b) \leq 10^8$。