AT_codequeen2026_h 迷子の森

公主高桥在森林中迷路了。 森林里有 $N$ 个广场和 $M$ 条道路。每个广场编号从 $1$ 到 $N$。第 $i$ 条道路连接广场 $a_i$ 和广场 $b_i$（是双向的），这条道路的宽度为 $c_i$，长度为 $d_i$。可能存在多条道路连接同一对广场。此外，从任意一个广场出发，总是可以通过若干条道路到达任意另一个广场。 森林中有 $K$ 只动物。第 $j$ 只动物最初位于广场 $v_j$，大小为 $x_j$。大小为 $x$ 的动物只能通过宽度不小于 $x$ 的道路。 高桥最初位于广场 $1$，并且没有骑任何动物。她可以无限次进行以下操作： - 没有骑动物时，可以选择一条道路步行移动到相邻广场。这时，她的步行距离增加该道路的长度。 - 没有骑动物时，可以骑上与自己在同一广场的任意一只动物。 - 骑着动物时，可以选择一条该动物可以通过的道路，和该动物一起移动到相邻广场。这时，她的步行距离不增加。 - 骑着动物时，可以下动物，动物留在当前广场。 高桥可以无视道路宽度，步行时可以通过任何道路。同时，她不能在道路中途上下动物或者停下来。动物只有在高桥骑着行进时才会移动，其他情况不会自行移动。 请你求出，高桥到达广场 $N$ 最少需要步行的距离。

输入按以下格式从标准输入给出。 > $N$ $M$ $K$ > $a_1$ $b_1$ $c_1$ $d_1$ > $a_2$ $b_2$ $c_2$ $d_2$ > $\vdots$ > $a_M$ $b_M$ $c_M$ $d_M$ > $v_1$ $x_1$ > $v_2$ $x_2$ > $\vdots$ > $v_K$ $x_K$

输出答案。

### 样例解释 1 如果按以下方式行动，步行距离为 $3$： - 从广场 $1$ 通过道路 $1$ 步行到广场 $2$，步行距离增加到 $3$。 - 在广场 $2$ 骑上动物 $1$。 - 骑着动物，使用道路 $2$ 到达广场 $3$。 - 骑着动物，使用道路 $3$ 到达广场 $4$。 ### 样例解释 2 如果按以下方式行动，步行距离为 $7$： - 在广场 $1$ 骑上动物 $1$。 - 骑着动物，使用道路 $1$ 到达广场 $2$。 - 在广场 $2$ 下动物，动物 $1$ 留在广场 $2$。 - 步行通过道路 $2$ 走到广场 $3$，步行距离为 $7$。 注意，因为道路 $2$ 的宽度为 $2$，而动物 $1$ 的大小为 $5$，所以它无法通过该道路。 ### 数据范围 - $2 \le N \le 10^5$ - $N-1 \le M \le 10^5$ - $1 \le K \le 10^5$ - $1 \le a_i < b_i \le N$ - $1 \le c_i, d_i \le 10^9$ - $1 \le v_j \le N$ - $1 \le x_j \le 10^9$ - 所给的图保证联通 - 输入均为整数 由 ChatGPT 5 翻译