활자 그래프

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

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

$t$번 활자 그래프는 $N_t$개의 번호가 붙은 정점으로 이루어져 있으며, 정점에는 1 이상 $N_t$ 이하의 번호가 붙어 있다. 이후 다음 두 가지 작업 중 하나를 반복해서 $t$번 활자 그래프를 완성한다.

• 번호가 붙은 $v$번 정점에서 $w$번 정점으로 가는 가중치가 있는 단방향 간선을 추가한다.
• $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$개의 줄에 정수 $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을 출력한다.