P1075星门待群钥（gateway）

【题目背景】

穿过云海后，tfbz 抵达了由古老星门连接的高空驿站。每座星门都在等待若干枚散落于其他区域的星钥，只有群钥尽数归位，通往内陆的航路才会真正开启。

【题目描述】

驿站群中共有 $n$ 个区域，依次编号为 $1\sim n$。每个区域都保存着一枚星钥，当探索信号首次进入一个区域时，这里的星钥便立即归位。区域之间有 $m$ 条单向航路，第 $j$ 条航路从区域 $u_j$ 通向区域 $v_j$，沿这条航路传递探索信号需要 $w_j$ 个单位时间。

探索信号最初在 $0$ 时刻进入区域 $1$。一旦某个区域被信号进入，就可以立即从这里沿任意航路继续传递，并且不同航路上的传递可以同时进行。

每个区域还对应一座星门。区域 $i$ 的星门要求若干个前置区域中的星钥先归位。信号只有同时满足下面两个条件，才能进入区域 $i$：

• 已经有一束信号沿某条航路抵达区域 $i$。
• 区域 $i$ 要求的所有前置区域中的星钥都已经归位。

若信号沿航路提前抵达，它会停留在星门前等待，直到全部前置条件满足。区域 $1$ 不要求任何前置区域。

题目保证所有区域最终都能够被信号进入。请你求出信号首次进入每个区域的最早时刻。

形式化题意：给定一张带非负边权的有向图与每个区域的前置集合 $\operatorname{pre}_i$，求逐点最小非负整数序列 $\{t\}$，满足

其中空集合的最大值约定为 $0$。

【输入格式】

从文件 $\textbf{\textit{gateway.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个整数 $n,m$，分别表示区域数量与单向航路数量。

接下来 $m$ 行，第 $j$ 行包含三个整数 $u_j,v_j,w_j$，表示一条从区域 $u_j$ 通向区域 $v_j$、用时为 $w_j$ 的航路。

接下来 $n$ 行，第 $i$ 行首先包含一个非负整数 $k_i$，表示区域 $i$ 要求的前置区域数量，随后包含 $k_i$ 个互不相同的正整数，表示这些前置区域的编号。

【输出格式】

输出到文件 $\textbf{\textit{gateway.out}}$ 中。

对于每组测试数据输出一行 $n$ 个整数，第 $i$ 个整数表示信号首次进入区域 $i$ 的最早时刻。

【样例 1 输入】

10 224 431 2 341 3 252 4 263 4 1708091 2101 3113 3121 2 5131 3 1143 2 1150161 3170

【样例 1 输出】

10 3 3 420 2 1

【说明/提示】

【样例 1 解释】

在第一组测试数据中，信号会在第 $2$ 个单位时间抵达区域 $3$ 的星门，但区域 $3$ 仍在等待区域 $2$。区域 $2$ 在第 $3$ 个单位时间被进入，此时区域 $3$ 也可以立即被进入。随后信号再用 $1$ 个单位时间抵达区域 $4$，因此区域 $4$ 的最早进入时刻为 $4$。

【样例 2】

见选手目录下的 $\textbf{\textit{gateway/gateway2.in}}$ 和 $\textbf{\textit{gateway/gateway2.ans}}$。

该组样例符合测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{gateway/gateway3.in}}$ 和 $\textbf{\textit{gateway/gateway3.ans}}$。

该组样例符合测试点 $4\sim 7$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{gateway/gateway4.in}}$ 和 $\textbf{\textit{gateway/gateway4.ans}}$。

该组样例符合测试点 $8\sim 11$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{gateway/gateway5.in}}$ 和 $\textbf{\textit{gateway/gateway5.ans}}$。

该组样例符合测试点 $12\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{gateway/gateway6.in}}$ 和 $\textbf{\textit{gateway/gateway6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

\newpage

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10$，$1\leq n\leq 2\times 10^5$，$0\leq m,s\leq 5\times 10^5$，$1\leq u_j,v_j\leq n$，$u_j\ne v_j$，$0\leq w_j\leq 10^9$，其中 $s=\sum k_i$。对于同一个测试点，保证 $\sum n\leq 2\times 10^5$，$\sum m,\sum s\leq 5\times 10^5$。

特殊性质 A：每条航路均满足 $u_j<v_j$，每个前置区域的编号也都小于等待它的区域编号。

特殊性质 B：所有区域都不要求前置区域，也就是 $s=0$。