28399번 - 황혼

문제

오스타니아는 $N$개의 도시와 이를 잇는 $M$개의 도로로 구성된 나라이다. 도시는 1ドル$번부터 $N$번까지 차례대로 번호가 붙어 있으며, $i$ $(1\le i\le M)$번째 도로는 $u_i$번 도시에서 $v_i$번 도시로 가는 단방향 도로이다. $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})$로 구성되며, $p_{j,t}$번 도시에서 $p_{j,t+1}$번 도시로 가는 도로가 존재한다. $(1\le t<s_j)$ 어떤 도시도 서로 다른 두 개의 정보에 동시에 속해 있지 않다.

웨스탈리스의 첩보원 코드네임 <황혼>은 현재 오스타니아의 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. 1번과 2번 조건을 충족하면서 $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} )$

1ドル+i$번째 줄에는 오스타니아의 도로를 나타내는 $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+1$개의 정수 $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을 출력한다.

제한

힌트