황혼

오스타니아는 $N$개의 도시와 이 도시들을 잇는 $M$개의 도로로 이루어진 나라이다. 도시는 $1$번부터 $N$번까지 차례대로 번호가 붙어 있다. $i$ $(1\le i\le M)$번째 도로는 $u_i$번 도시에서 $v_i$번 도시로 가는 단방향 도로이며, 이 도로를 지나는 데 $w_i$만큼의 시간이 걸린다. 두 도시 사이에는 방향별로 도로가 최대 1개 있다. 편의상 $u$번 도시에서 $v$번 도시로 가는 도로를 지나는 데 걸리는 시간을 $w(u,v)$라고 하자.

웨스탈리스는 오스타니아와 냉전 관계에 있는 국가이다. 웨스탈리스는 첩보원들을 통해 오스타니아에 대한 $K$개의 정보를 얻었다. 각 정보는 하나의 단순 경로로 표현된다. 정확히는 $j$ $(1\le j\le K)$번째 정보가 서로 다른 $s_j$개 도시의 나열 $(p_{j,1},p_{j,2},\cdots ,p_{j,s_j})$이며, 모든 $1\le t<s_j$에 대해 $p_{j,t}$번 도시에서 $p_{j,t+1}$번 도시로 가는 도로가 존재한다. 어떤 도시도 서로 다른 두 정보에 동시에 속하지 않는다.

웨스탈리스의 첩보원 코드네임 <황혼>은 현재 오스타니아의 1번 도시에 있다. 웨스탈리스 정부는 정보를 모으기 위해 황혼에게 $x$번 도시까지 이동하라고 지시했다. 황혼은 정보 수집 효율을 최대화하려고, $K$개의 단순 경로 중 어느 것도 포함하지 않는 경로로 이동하기로 했다. 구체적으로 황혼이 방문한 도시를 차례대로 $(q_1,q_2,\cdots ,q_l)$이라 하면 다음 조건을 모두 만족해야 한다.

1. $q_i$번 도시에서 $q_{i+1}$번 도시로 가는 도로가 존재한다. $(1\le i<l)$
2. $(p_{z,1},p_{z,2},\cdots ,p_{z,s_z}) =(q_i,q_{i+1},\cdots ,q_{i+s_z-1})$를 만족하는 정수 $i$와 $z$가 존재하지 않는다.
3. 위 두 조건을 만족하면서 $x$번 도시까지 가는 데 걸리는 시간 $(=\sum_{i=1}^{l-1}w(q_i,q_{i+1}))$이 최소가 되어야 한다.

$1$ 이상 $N$ 이하의 모든 정수 $x$에 대해, 황혼이 $x$번 도시까지 이동할 수 있는지 판별하고, 이동할 수 있다면 $x$번 도시까지 가는 데 걸리는 시간을 계산하라.

첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(2\le N\le 2\times 10^5;$ $1\le M\le 3\times 10^5;$ $0\le K\le\frac{N}{2} )$

두 번째 줄부터 $M$개의 줄에는 각각 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다. 임의의 $i$에 대해 $u_i$번 도시에서 $v_i$번 도시로 가는 도로는 하나뿐이다. $(1\le i\le M;$ $1\le u_i,v_i\le N;$ $1\le w_i\le 10^9;$ $w_i$는 정수$;$ $u_i\neq v_i)$

$1+M+j$번째 줄에는 단순 경로를 나타내는 $s_j$와 $p_{j,1}, \cdots, p_{j,s_j}$가 공백으로 구분되어 주어진다. $K$개의 단순 경로에서 각 도시는 최대 $1$번 나타나며, 입력에 주어진 순서대로 도로를 따라 이동할 수 있음이 보장된다. $(1\le j\le K;$ $s_j\ge 2;$ $\sum_{j=1}^{K}s_j\le N)$

공백으로 구분된 $N$개의 정수를 첫 번째 줄에 출력한다. $i$번째 정수는 황혼이 모든 조건을 만족하며 $i$번 도시까지 가는 데 걸리는 시간이다. $i$번 도시에 도달할 수 없다면 -1을 출력한다.