T638244 小 B 的旅程

生火间，一人一火堆，建立村落……

小 B 在 cw 集训了一周后，他想家了（其实就是想跑了），于是他决定踏上回家的征途。 小 B 所在的城市整体是一张无向图，一共有 $N$ 个点、$M$ 条边，且任意一条边有一个边权 $s_i$，已知 cw 在 $1$ 号节点，他的家在 $N$ 号节点。 小 B 为了能顺利到家，他买了个体积为 $V$ 的包用来装熏肉，每个熏肉所占的体积都是 $1$，且他有 $L$ 块熏肉。 小 B 为了在半路不会被饿死，于是他决定带着所有的熏肉出发，并且不会在路上扔掉一块熏肉（如果有带不走的熏肉，那他也没办法）。 当然，小 B 可以选择先走 $x$ 的任意距离，然后挖个洞把他带的所有熏肉埋进去然后再回去搬熏肉，所在节点若埋了熏肉，那么埋下的肉可取出来小于等于埋下数量的熏肉且不需要任何消耗（买下的熏肉数量也要减少取出数量），**此操作只在节点处进行。** 在小 B 回家的路上会有很多贸易站（保证这些贸易站都在节点上，且起点与终点都没有贸易站），在第 $i$ 处贸易站，小 B 可以选择卖掉一部分熏肉来换钱，且小 B 每卖掉一块熏肉就可以获得 $a_i$ 的钱，但是第 $i$ 处贸易站最多只能接受 $b_i$ 块熏肉。 已知小 B 每走一个单位距离就要吃一块熏肉，小 B 想知道在他能回到家的前提下，他最多能获得多少钱。如果无论如何都无法回到家，请输出 `-1`。

输入第一行四个整数 $N,M,V,L$，表示图的点数、边数、背包容量、初始熏肉个数。 输入第 $2\sim M+1$ 行，每行输入三个整数 $x_i,y_i,z_i$，表示节点 $x_i$ 与节点 $y_i$ 之间有一条无向边，边权为 $z_i$。 输入第 $M+2\sim M+N+1$ 行，每行三个整数 $op_i,a_i,b_i$，$op_i$ 表示该节点是否有贸易站，如果是 $1$ 则有，如果是 $0$ 则没有，且如果是 $0$，那么 $a_i$ 与 $b_i$ 都为 $0$。

输出仅一行，表示小 B 到家后能得到的最大钱数。如果无论如何都到不了，那么输出 `-1`。

**样例一解释：** - 初始熏肉 $20$ 块，背包体积 $V=10$。 1. 节点 $1$ 到节点 $2$（边权为 $1$）： - 第一次移动：带 $10$ 块熏肉从 $1$ 走到 $2$，消耗 $1$ 块熏肉，背包里剩 $9$ 块；在节点 $2$ 埋 $8$ 块熏肉，带 $1$ 块返回 $1$，消耗 $1$ 块，到 $1$ 时背包内肉的数量为 $0$。节点 $1$ 库存剩 $10(20-10)$ 块。 - 第二次：带 $10$ 块（剩余全部）直接从 $1\to2$，消耗 $1$ 块，剩 $9$ 块；此时节点 $2$ 总库存：$9+8=17$ 块。 2. 在节点 $2$ 处卖肉： - 节点 $2$ 有贸易站，卖肉单价 $a_i=1$，最多可卖 $b_i=3$ 块。 - 卖出 $3$ 块，获得 $3\times1=3$ 元，剩余熏肉 $14$ 块（$17-3=14$）。 3. 节点 $2$ 到节点 $3$（边权为 $1$）： - 起始节点 $2$ 库存 $14$ 块。 - 第一次：带 $10$ 块从 $2\to3$，消耗 $1$ 块，剩 $9$ 块；在节点 $3$ 埋 $8$ 块，带 $1$ 块返回 $2$，消耗 $1$ 块，到 $2$ 时背包内肉的数量为 $0$。节点 $2$ 库存剩 $4（14-10）$ 块，节点 $3$ 库存 $8$ 块。 - 第二次：带 $4$ 块（剩余全部）从 $2\to3$，消耗 $1$ 块，剩 $3$ 块；此时节点 $3$ 总库存：$8+3=11$ 块。 4. 节点 $3$ 到节点 $4$（边权为 $2$）： - 第一次：带 $10$ 块熏肉从 $3\to4$，到节点 $4$ 时剩余 $8$ 块，因为在节点 $3$ 剩余的一块无论如何都带不回来，所以舍弃。 5. 在节点 $4$ 卖肉： - 节点 $4$ 有贸易站，卖肉单价 $a_i=2$，最多可卖 $b_i=5$ 块。 - 卖出 $5$ 块，获得 $5\times2=10$ 元，剩余熏肉 $3$ 块（$8-5=3$）。 5. 节点 $4$ 到节点 $5$（边权为 $3$）： - 带着最后的 $3$ 块熏肉直接走到 $5$ 号节点，正好用完所有熏肉且安全到家。 最终赚钱 $13$ 元。 **数据范围：** 对于所有数据，保证 $N\le100 $，$M\le\min\{2\times10^3,\cfrac{N(N+1)}{2}\}$，$V,L\le100$，$x_i,y_i\le N$，$z_i\le100$，$op_i\isin\{0,1\}$，$a_i\le10$，$b_i\le L$。