题目描述

$114514$ 国即将召开会议，部长 $\texttt{\color{black}j\color{red}iayelin}$ 及他的 $1919810$ 大军需要从 fls 出发在下午之前赶到各个城市 $2$ ~ $n$ 专门邀请

$114514$ 国有 $n$ 座城市

由于 $114514$ 国交通网络很高级，有 $k$ 条超级铁路和 $m$ 条航线

对于航线，你坐的是私人飞机，任意时刻都可坐从 $u$ 到 $v$ 或从 $v$ 到 $u$，且告诉你要 $w$ 刻时间

每条铁路（单向）该班在 $t_1$ 时刻从 $a_1$ 发车，并在 $t_j$ 时刻到达 $a_j$

每次换乘不要时间，忽略发车及到达停站时间。

现在时刻是 $0$ ，请问从 fls（编号为 $1$）到 $2$ ~ $n$ 分别要最短时间是多少

以及你需要回来（第二天时刻 $0$），你只需要告诉 $\texttt{\color{black}j\color{red}iayelin}$ 最长的一个人花的时间即可

输入格式

第一行三个整数分别为 $n$,$m$,$k$

接下来 $m$ 行每行三个整数 $u,v,w$

接下来 $k$ 行每行先是一个整数表示停站数量 $p_i$（包括起始站），接着 $p_i$ 对整数 $t_{j}$,$a_j$ 表示到达时间和城市编号

以上数据均为正整数

输出格式

先一行 $n-1$ 整数，表示到 $i$ 最短时间，到不了输出 $-114514$

随后一行一个整数，表示最长的一个人返回花的时间（不包括回不来的人，但包括去不了但回得来的人，毕竟实在不行可以发 $\texttt{jyl chat v19.19.810}$ 请过来）

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

2 15 10 18
131

提示

样例解释

样例一

去

到 $2$ : 从 $1$ 飞到 $2$，总费时 $2$

到 $4$ : 从 $1$ 飞到 $2$，在时刻 $3$ 坐上第一辆高铁，时刻 $10$ 在 $4$ 下车，总费时 $10$

到 $3$ : 从 $1$ 飞到 $2$，在时刻 $3$ 坐上第一辆高铁，时刻 $10$ 在 $4$ 下车，等待到时刻 $12$ 坐第二班车，在时刻 $15$ 在 $3$ 号点下车，总费时 $15$

到 $5$ : 从 $1$ 飞到 $2$，在时刻 $3$ 坐上第一辆高铁，时刻 $10$ 在 $4$ 下车，等待到时刻 $12$ 坐第二班车，在时刻 $15$ 在 $3$ 号点下车，从 $3$ 飞到 $5$ 总费时 $18$

回

$2,3,4,5$ 回来时间分别为 $2$，$116$，$131$,$119$ 最大 $131$

数据范围

设所有数据及答案为 $x$ ，则 $-2\times 10^9 \le x \le 2\times 10^9$

设 $s$ 表示 $\sum^k_{i=1}p_i$

测试点编号	n	m	s
1~2	$\le 500$
3~4	$\le 10^4$	$\le 10^4$	$=0$
5~6		$=0$	$\le 10^4$
7~20		$\le 10^4$