T3

题目描述

小王的演唱会将在今晚九点开始，但你发现时间不多了，所以你需要尽快赶到现场。

城市的步行地图可以抽象为一张 $n$ 个点 $m$ 条边的带权无向图。（可能存在重边、自环）

你现在在 $1$ 号节点，小王的演唱会将在 $n$ 号节点举行。

对于一条连接 $u,v$ ，边权为 $w$ 的边，你可以花费 $w$ 的时间从 $u$ 走到 $v$ ，也可以花费 $w$ 的时间从 $v$ 走到 $u$ 。保证所有 $w$ 均为正整数。

你不仅可以走路，还可以坐公交车。你查到了最近将有 $k$ 班公交车。其中第 $i$ 班将在 $t_{i,1}$ 时刻从 $a_{i,1}$ 号节点发车，并在 $t_{i,j}$ 的时刻到达 $a_{i,j}$ 号节点。（由于车走的时间肯定是正的，所以保证 $t_i$ 单调递增。而 $a_i$ 可能重复，即车在多个不同时刻到达一个相同的节点。）

你可以在任意位置停留任意长度的时间，也可以在公交车所停的任意站在指定时间上下车。上下车不需要耗费时间，且可以在恰好发车的那一时刻上车。

现在是时刻 $0$ 。请问你从 $1$ 号点到达 $n$ 号点所需的最短时间是多少？

输入格式

第一行三个整数 $n,m,k$ 。

接下来 $m$ 行每行三个整数 $u_i,v_i,w_i$ ，描述一条边。

接下来 $k$ 行，每行开头一个整数表示这班车的停站数量 $p_i$，紧接着 $p_i$ 对整数 $t_{i,j},a_{i,j}$ ，表示一个停站的时间和位置。

输出格式

输出一行一个整数，表示最短时间。

如果无法从 $1$ 到达 $n$ ，那么输出一个数字 $-1$ 。

样例1输入

5 4 2
1 2 2
2 3 114
3 4 514
3 5 3
3 3 2 10 4 20 3
3 12 4 15 3 20 5

样例1输出

18

样例1解释

首先从 $1$ 走到 $2$ ，并等待至时刻 $3$ 。

然后在时刻 $3$ 在 $2$ 号点坐上第一班车，并在时刻 $10$ 是在 $4$ 号点下车。

然后等待到时刻 $12$ 上第二班车，在时刻 $15$ 时在 $3$ 号点下车。

最后从 $3$ 号点走到 $5$ 号点，总共花费时间为 $18$ 。

数据范围

令 $s$ 表示 $\Sigma_{i=1}^k p_i$ ，即所有车的停站总数之和。

对于 $20\%$ 的数据，满足 $n\leq 5,m\leq 5,s\leq 5$ 。

对于另外 $20\%$ 的数据，满足 $n\leq 1000,m\leq 1000,s\leq 100$ 。

对于另外 $20\%$ 的数据，满足 $k=0$ 。

对于另外 $20\%$ 的数据，满足 $m=0$ 。

对于 $100\%$ 的数据，满足 $n\leq 10^5,m\leq 3\times 10^5,s\leq 3\times 10^5,w_i\leq 10^9,t_i\leq 10^9$ 。