Problem Background

Data has been updated.

After several days and nights of intense gaming, Xiao Mai has finally reached the final level, which is also the devil level of $Dancing Line$ — $The Legend of Assassin$.

Problem Description

As shown in the figure, the devil level often features exploding roads and sudden obstacles.

Xiao Mai is troubled because she does not know the complete map. Therefore, she has made many attempts and summarized the roads that appear or disappear over time and her positions at those moments. To simplify the problem, we assume that Xiao Mai's position remains unchanged.

Now, she wants to know the earliest moment from which she can see a path leading to the end. Additionally, since some paths contain diamonds that provide certain points, Xiao Mai also wants to know the maximum score she can achieve by following the current map to the end at the earliest moment she can see a path to the end.

Input Format

The first line contains two numbers, $n$ and $m$, representing the number of nodes in the map and the initial number of edges, respectively. Nodes are numbered from $1$ to $n$. Initially, at time $0$, Xiao Mai is at node $1$, and the end is always at node $n$.

The next $m$ lines each contain three numbers, $u_i$, $v_i$, and $w_i$, representing an edge from $u_i$ to $v_i$ with a score of $w_i$.

The next line contains an integer $t$, representing the number of moments when new edges appear or old edges disappear. If no edges appear or disappear, $t = 0$.

The next $t$ lines each start with a number $tm_j$, representing the moment of the event. The second number is $type$. If $type == 0$, it indicates a new edge appears, followed by three numbers $u_j$, $v_j$, and $w_j$, representing the edge information (same as above). If $type == 1$, it is followed by a number $k$, indicating that the $k$-th road that has not disappeared at the current moment disappears.

Output Format

If it is impossible to reach the end at any moment, output "Continue from the last checkpoint". Otherwise, output two lines: the first line is a number $tmp$, representing the earliest moment when a path to the end is visible; the second line is a number $score$, representing the maximum score that can be achieved at that moment.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0
2

Sample Input #2

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

Sample Output #2

Continue from the last checkpoint

Sample Input #3

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

Sample Output #3

2
1

Notes/Hints

This problem consists of $10$ test cases, with detailed information for each test case 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 edge scores are $0$; Score: $10$;

$4$: $n <= 100000$, $m <= 200000$, $t = 0$; No new or disappearing edges; Score: $5$;

$5$ to $6$: $n <= 100000$, $m <= 200000$, $t <= 100000$; No disappearing edges; Score: $10$;

$7$ to $8$: $n <= 100000$, $m <= 200000$, $t <= 100000$; No new edges; Score: $10$;

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

Additionally, for all data, $0 < u_i, u_j, v_i, v_j <= n$, $0 <= w_i, w_j <= 10$, $0 < tm_j <= 10t$, and $tm_j$ are distinct; the data guarantees no positive cycles.

见题面 Input 部分

见题面 Output 部分