该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在 星空草原 的尽头，噜噜与“一只羊”发现了两种神秘水晶：

• 幽蓝晶石（免费水晶）── 把传送带耗时变为 0；
• 琥珀晶石（折扣水晶）── 把传送带耗时变为 $\left\lfloor\frac{w}{2}\right\rfloor$。

问题描述

给定一张带正权有向图，顶点编号 $1\ldots N$。你可在出发前任选至多 A 条边安装幽蓝晶石、至多 B 条边安装琥珀晶石（两类不可重叠，同一条边至多安装一种）。旅途中走过已安装水晶的边时按优惠耗时，其余按原权耗时。求从 1 号羊圈到 $N$ 号羊圈的最短总耗时；若无法到达输出 $-1$。

输入格式

第一行 N M A B。 接下来 M 行，每行 u v w 表示一条有向边 $u\to v$，耗时 $w$（$1\le w\le10^{9}$）。

输出格式

一行一个整数——最短耗时；若不可达输出 -1。

样例

5 6 1 1
1 2 5
2 5 7
1 3 2
3 4 2
4 5 2
3 2 1

2

样例解释 可以选择路径 1→2→5，共两条边，原权分别为 5 和 7。

• 对边 2→5 使用“免费水晶”，耗时变为 0；
• 对边 1→2 使用“折扣水晶”，耗时变为 ⌊5/2⌋ = 2； 因此总耗时为 0 + 2 = 2。 （也可选路径 1→3→2→5：分别对 2→5 用免费，对 1→3 或 3→2 用折扣，结果同样为 2。）

数据范围与约定

• $1\le N\le100\,000$，$1\le M\le300\,000$
• $0\le A,B\le30$，且 $A+B\ge1$
• 保证不存在负权边与负环
• 保证图随机生成