题目描述

给定一个 $n$ 个点 $m$ 条边的有向带权图，以及一个起点 $s$ 和一个终点 $t$，你有一次机会，可以将其中一条边权的权值变为 $\lfloor \dfrac{边权}{2} \rfloor$，求操作后图的最短路。
若无法到达，输出 -1。

输入格式

第一行输入四个整数 $n,m,s,t$
接下来 $m$ 行，每行三个整数 $u, v, w$ 表示点 $u$ 和点 $v$ 之间有一条长度为 $w$ 的边。

输出格式

第一行一个整数，表示其最短路。

数据范围

$1 \le n \le 10 ^ 5, 1 \le m \le 4 \times 10 ^ 5 \\ 1 \le u, v \le n, 1 \le v \le 10 ^ 4$。