황혼

오스타니아는 $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을 출력한다.