Twilight

Ostania is a country with $N$ cities and $M$ roads connecting them. The cities are numbered from $1$ to $N$. The $i$-th road $(1\le i\le M)$ is a one-way road from city $u_i$ to city $v_i$, and traveling along it takes $w_i$ time. Between any two distinct cities, there is at most one road in each direction. For convenience, let $w(u,v)$ be the time needed to travel along the road from city $u$ to city $v$.

Westalis is a country in a Cold War rivalry with Ostania. Through several agents, Westalis obtained $K$ pieces of information about Ostania. Each piece is represented by a simple path. Precisely, the $j$-th piece $(1\le j\le K)$ is a sequence of $s_j$ distinct cities $(p_{j,1},p_{j,2},\cdots ,p_{j,s_j})$, and for every $1\le t<s_j$ there is a road from city $p_{j,t}$ to city $p_{j,t+1}$. No city belongs to two different pieces of information at the same time.

Twilight, the agent codenamed , is currently in city $1$ of Ostania. The Westalis government orders Twilight to travel to city $x$ to collect information. To maximize the efficiency of the collection, Twilight decides to take a route that contains none of the $K$ simple paths. Specifically, let $(q_1,q_2,\cdots ,q_l)$ be the cities Twilight visits in order. Then all of the following must hold.

1. There is a road from city $q_i$ to city $q_{i+1}$. $(1\le i<l)$
2. There are no integers $i$ and $z$ such that $(p_{z,1},p_{z,2},\cdots ,p_{z,s_z}) =(q_i,q_{i+1},\cdots ,q_{i+s_z-1})$.
3. Among all routes that satisfy conditions 1 and 2, the total time to reach city $x$, $(=\sum_{i=1}^{l-1}w(q_i,q_{i+1}))$, is minimal.

For every integer $x$ with $1\le x\le N$, determine whether Twilight can reach city $x$, and if so, compute the time it takes to reach city $x$.

The first line contains three integers $N$, $M$, and $K$ separated by spaces. $(2\le N\le 2\times 10^5;$ $1\le M\le 3\times 10^5;$ $0\le K\le\frac{N}{2} )$

Each of the next $M$ lines contains $u_i$, $v_i$, and $w_i$ separated by spaces. For each $i$, the road from city $u_i$ to city $v_i$ is unique. $(1\le i\le M;$ $1\le u_i,v_i\le N;$ $1\le w_i\le 10^9;$ $w_i$ is an integer$;$ $u_i\neq v_i)$

Line $1+M+j$ contains $s_j$ followed by the $s_j$ integers $p_{j,1}, \cdots, p_{j,s_j}$ of the simple path, separated by spaces. For the $K$ simple paths, each city appears at most once, and it is guaranteed that the path can be traversed along the roads in the order given in the input. $(1\le j\le K;$ $s_j\ge 2;$ $\sum_{j=1}^{K}s_j\le N)$

Print $N$ integers separated by spaces on the first line. The $i$-th integer is the time it takes Twilight to reach city $i$ while satisfying all the conditions. If city $i$ cannot be reached, print -1.