Movable Type Graph

In the Goryeo period, the scholar Ha Uibi made graphs by printing them with metal movable type. While doing this, Ha Uibi became curious about the shortest path in a type graph, the name for a graph printed with type.

Ha Uibi currently has $T$ type graphs, numbered from 1 to $T$ in the order they were made.

Type graph $t$ has $N_t$ numbered vertices, from 1 to $N_t$. Type graph $t$ is then completed by repeatedly doing one of the following.

• Add a directed edge with weight from vertex $v$ to vertex $w$.
• Print the $i$-th type graph so that its start and end points are vertices $v$ and $w$ of graph $t$. Its vertices and edges are added to graph $t$. The vertices of the printed $i$-th graph are not numbered. ($1 \le i < t$)

The start vertex of every type graph is vertex 1, and its end vertex is vertex 2.

Find the shortest path from vertex 1 to vertex 2 in type graph $T$.

The first line contains the number of type graphs $T$. ($1 \le T \le 100\,000$)

The information for each type graph is given as follows.

Suppose you are reading type graph $t$.

• The first line contains the number of numbered vertices $N_t$ and the number of edge or sub-graph operations $M_t$, separated by a space. ($2 \le N_t \le 200\,000$, $0 \le M_t \le 500\,000$)
• The next $M_t$ lines each contain three integers $v$, $w$, and $x$, separated by spaces. ($1 \le v, w \le N_t$, $v \ne w$, $-(t-1) \le x \le 10^9$)
  • If $x \ge 0$, a directed edge with weight $x$ from vertex $v$ to vertex $w$ was added.
  • If $x < 0$, the type graph $|x|$ was printed with its start point at vertex $v$ and its end point at vertex $w$.

The sum of the numbered vertex counts does not exceed $200\,000$. The sum of the edge and sub-graph operation counts does not exceed $500\,000$.

Print the length of the shortest path from vertex 1 to vertex 2 in type graph $T$. If there is no path from vertex 1 to vertex 2, or if this value is greater than $10^{18}$, print -1.