走走走

题号：NC231669
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给你一个有向带权图,你从 $s$ 点出发到 $t$ 点,走一条权值为w的边需要花费 $w$ .

现在你可以使用赖皮魔法,白走一条边,不用给任何花费,问 $s$ 点到 $t$ 点的最小花费

比如给如下图, $V_1$ 号点到 $V_0$ 号点,最小花费走法为 $V_1->V_0$ ,去掉一条边,花费只为 $0$ 。

可能存在自环和重边,如果 $s$ 走不到 $t$ 点,输出 $-1$ 。

输入描述:

第一行输出两个数,和,代表点的个数,代表边数
第二行输出两个数,和,代表从点到
接下来行,每行为代表到的有向边,权值为

输出描述:

输出一行,代表从到新最短路径权值和

示例1

输入

复制

输出

复制