활자 그래프

고려 시대의 학자 하의비는 금속 활자를 사용해서 그래프를 찍어 내는 작업을 하고 있었다. 그러던 중, 하의비는 활자로 찍어내던, 일명 활자 그래프에서의 최단 경로가 궁금해졌다.

하의비는 현재 $T$개의 활자 그래프를 가지고 있으며, 만든 순서대로 $1$번부터 $T$번까지의 번호가 매겨져 있다.

$t$번 활자 그래프는 $N_t$개의 번호가 붙은 정점으로 이루어져 있으며, 각각의 정점에는 $1$ 이상 $N_t$ 이하의 번호가 붙어있다. 이후, 다음과 같이 번호가 붙은 정점들 사이에 간선이나 이전에 만들었던 활자 그래프를 찍어내는 방식으로 $t$번 활자 그래프가 완성된다.

• 간선을 찍는 경우, $v$번 정점에서 $w$번 정점으로 가는 가중치가 있는 단방향 간선을 추가한다.
• $i$번째 활자 그래프를 찍는 경우, $i$번째 활자 그래프의 시작점과 끝점이 $t$번 활자 그래프의 $v$번 정점과 $w$번 정점이 되도록 $i$번째 활자 그래프의 정점과 간선을 추가한다. 이 과정에서 생기는 $i$번째 활자 그래프의 정점들에는 번호가 붙지 않는다. $(1\le i<t)$

모든 활자 그래프의 시작점은 $1$번 정점이고, 끝점은 $2$번 정점이다.

이때, $T$번 활자 그래프의 $1$번 정점에서 $2$번 정점으로 가는 최단 경로를 구해 보자.

첫 번째 줄에 활자 그래프의 개수 $T$가 주어진다. $(1\le T\le 100\, 000)$

이후, 각각의 활자 그래프에 대한 정보가 다음과 같이 주어진다.

• 현재 $t$번 활자 그래프를 입력받는다고 해보자.

• 첫 번째 줄에는 $t$번 활자 그래프의 번호가 붙은 정점의 개수 $N_t$와 간선이나 다른 활자 그래프를 찍은 횟수 $M_t$가 공백으로 구분되어 주어진다. $(2\le N_t\le 200\, 000;$ $0\le M_t\le 500\, 000)$

• 이후 $M_t$개의 줄에 걸쳐 $3$개의 정수 $v,w,x$가 공백으로 구분되어 주어진다. $(1\le v,w\le N_t;$ $v\ne w;$ $-(t-1)\le x\le 10^9)$

  • $x\ge 0$이라면, 이는 $v$번 정점에서 $w$번 정점으로 가는 가중치 $x$의 단방향 간선을 찍었음을 의미한다.
  • $x<0$이라면, 이는 $v$번 정점을 시작점에 맞추고 $w$를 끝점에 맞춰서 $|x|$번 활자 그래프를 찍었음을 의미한다.

번호가 붙은 정점의 개수의 합은 $200\, 000$을 넘지 않으며, 간선이나 다른 활자 그래프를 찍은 횟수의 합은 $500\, 000$을 넘지 않는다.

첫 번째 줄에 $T$번 활자 그래프에서, $1$번 정점에서 $2$번 정점으로 가는 최단 경로를 출력한다. 만약 $1$번 정점에서 $2$번 정점으로 가는 경로가 없거나, 이 값이 $10^{18}$보다 크다면 $-1$을 대신 출력한다.