Background

The testdata has been updated.

After several days and nights of intense grinding, Umaru finally reached the last level, the boss level of $Dancing$ $Line$ — $The$ $Legend$ $of$ $Assassin$.

Problem Description

As shown in the figure, the boss level often has broken roads and sudden obstacles.

Umaru is troubled because she does not know the complete map. So she made many attempts and summarized the roads that appear or disappear over time, and her position at those moments. To simplify the problem, we assume that Umaru's position never changes.

Now she wants to know: from what earliest moment can she see a path that can lead to the destination. Also, because there are diamonds on some paths and these diamonds can give extra points, Umaru also wants to know the maximum score she can obtain by going to the destination following the current map at the earliest moment when she can first see a path to the destination.

Input Format

The first line contains two integers $n$ and $m$, representing the number of nodes in the map and the number of initial edges. Nodes are numbered from $1-n$. Initially, this is time $0$. Umaru is at node $1$, and the destination is always node $n$.

The next $m$ lines each contain three integers $u_i$, $v_i$, $w_i$, describing an edge from $u_i$ to $v_i$ with score $w_i$.

The next line contains one integer $t$, representing the number of moments when a new edge appears or an old edge disappears. If no edge appears or disappears, then $t=0$.

The next $t$ lines describe events. In each line, the first number is $tm_j$, the time when this event happens. The second number is $type$:

• If $type==0$, it means a new edge appears. Then three numbers $u_j$, $v_j$, $w_j$ follow, describing the edge (same meaning as above).
• If $type==1$, then one number $k$ follows, meaning that at the current time, the $k$-th road among those that have not disappeared disappears.

Output Format

If at no time it is possible to reach the destination, output "$Continue$ $from$ $the$ $last$ $checkpoint$". Otherwise, output two lines:

• The first line contains one number $tmp$, the minimum time when a path to the destination can be seen.
• The second line contains one number $score$, the maximum score that can be obtained when reaching the destination at that time.

3 3
1 2 1
2 3 1
1 3 1
0

0
2

3 3
1 2 1
2 2 0
3 1 1
0

Continue from the last checkpoint

3 3
1 2 1
2 2 0
3 1 1
4
2 0 1 3 1
1 1 3
3 1 1
5 1 1

2
1

Hint

This problem has $10$ test points. The detailed information is as follows.

$1$: $n<=100000$, $m<=200000$, $t<=100000$. Output "$Continue$ $from$ $the$ $last$ $checkpoint$". Score: $5$.

$2$: $n<=100$, $m<=10000$, $t<=100$. No special properties. Score: $10$.

$3$: $n<=100000$, $m<=200000$, $t<=100000$. All edges have score $0$. Score: $10$.

$4$: $n<=100000$, $m<=200000$, $t=0$. No edges are added or removed. Score: $5$.

$5$~$6$: $n<=100000$, $m<=200000$, $t<=100000$. No edges disappear. Score: $10$.

$7$~$8$: $n<=100000$, $m<=200000$, $t<=100000$. No edges appear. Score: $10$.

$9$~$10$: $n<=100000$, $m<=200000$, $t<=100000$. No more than $1000$ edges disappear. Score: $15$.

In addition, for all data, $0<u_i,u_j,v_i,v_j<=n$, $0<=w_i,w_j<=10$, $0<tm_j<=10t$, and all $tm_j$ are distinct. The testdata guarantees that there is no positive cycle.

Translated by ChatGPT 5