AT_iroha2019_day2_g 通学路

※きたむー是协助出这道题的人名。另外，きたむー的女朋友不是いろはちゃん。 今天是きたむー和他的女朋友期待已久的“第一次一起采花”纪念日。他本应在今天送给女朋友 $K$ 朵花。然而，他因为要管理的纪念日太多，忘记买花了。于是他决定在上学途中买花。 きたむー居住的城市有 $N$ 个车站，每个车站编号为 $1$ 到 $N$。他所乘坐的铁路有 $M$ 条线路，第 $i$ 条线路连接车站 $A_i$ 和 $B_i$，票价为 $C_i$ 日元，可以双向通行。在车站 $j$，可以以 $Y_j$ 日元的价格不限量购买 $X_j$ 朵花的花束。きたむー住在车站 $1$ 附近，他的学校在车站 $N$ 附近。 那么，きたむー在买到不少于 $K$ 朵花后，通学所需的交通费与花费的总和最小值是多少？

输入按以下格式从标准输入给出。 > $N$ $M$ $K$ > $A_1$ $B_1$ $C_1$ > $A_2$ $B_2$ $C_2$ > $\vdots$ > $A_M$ $B_M$ $C_M$ > $X_1$ $Y_1$ > $X_2$ $Y_2$ > $\vdots$ > $X_N$ $Y_N$

请输出きたむー在买到不少于 $K$ 朵花后，通学所需的交通费与花费的总和的最小值。如果无法买到 $K$ 朵花，或者无法到达学校，则输出 `-1`。

### 限制条件 - 输入均为整数。 - $2 \leq N \leq 1000$ - $1 \leq M \leq 2000$ - $1 \leq K \leq 1000$ - $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq M)$ - $1 \leq C_i \leq 10^9$ $(1 \leq i \leq M)$ - $0 \leq X_j \leq K$ $(1 \leq j \leq N)$ - $1 \leq Y_j \leq 10^9$ $(1 \leq j \leq N)$ 2019/05/01 21:32 补充：由于限制条件中部分 $N$ 和 $M$ 写反，现已修正。 ### 题解 [题解](https://img.atcoder.jp/iroha2019-day2/editorial-G.pdf) ### 样例解释 1 从车站 $1$ 出发，经由车站 $2$、车站 $3$，到达车站 $4$。交通费总计为 $300$ 日元。在车站 $1$ 购买 $3$ 套，在车站 $4$ 购买 $1$ 套，则花费总计为 $38$ 日元。 ### 样例解释 2 请注意，购买的花可以超过 $K$ 朵。 由 ChatGPT 4.1 翻译