CF1870H.Standard Graph Problem

You are given a weighted directed graph with $n$ vertices and $m$ edges. Each vertex in the graph can be either highlighted or normal. Initially, all vertices are normal. The cost of the graph is defined as the minimum sum of edge weights that need to be selected so that from each normal vertex one can reach at least one highlighted vertex using the selected edges only. If it is not possible to select the edges, the cost is $-1$ instead.

Your task is to compute the cost of the graph after each of the $q$ queries. The queries can be of two types:

• $+\;v_i$ makes vertex $v_i$ highlighted; it is guaranteed that the vertex is normal before the query.
• $-\;v_i$ makes vertex $v_i$ normal; it is guaranteed that the vertex is highlighted before the query.

Output the cost of the graph after each of the $q$ queries.

给你一个包含 $n$ 个顶点和 $m$ 条有向边的带权有向图。图中每个顶点可以是“高亮的”或“普通的”。初始时，所有顶点均为普通顶点。图的“代价”定义为：为使得每个普通顶点仅通过所选边均能到达至少一个高亮顶点，所需选取的边的权重之和的最小值；若无法选出满足条件的边集，则代价为 $-1$。

你需要对接下来的 $q$ 个查询依次处理，并在每次查询后输出当前图的代价。查询分为两类：

• $+\;v_i$：将顶点 $v_i$ 设为高亮顶点；保证该顶点在查询前为普通顶点。
• $-\;v_i$：将顶点 $v_i$ 设为普通顶点；保证该顶点在查询前为高亮顶点。

请依次输出每次查询后的图的代价。

The first line contains three integers $n$, $m$, and $q$ ($3 \le n \le 2 \cdot 10^5, 1 \le m, q \le 2 \cdot 10^5$) — the number of vertices in the graph, the number of edges, and the number of queries.

The next $m$ lines contain the edges of the graph, one edge per line. The $i$-th line contains three integers $u_i$, $v_i$, and $c_i$ ($1 \leq u_i, v_i \leq n, u_i \ne v_i, 1 \leq c_i \leq 10^6$) — the endpoints of the $i$-th edge (from $u_i$ to $v_i$) and its weight ($c_i$).

The next $q$ lines contain the queries, one query per line. The $i$-th line contains $+\;v_i$, if it is a query of the first type, and $-\;v_i$, if it is a query of the second type ($1 \leq v_i \leq n$).

第一行包含三个整数 $n$、$m$ 和 $q$（$3 \le n \le 2 \cdot 10^5$，$1 \le m, q \le 2 \cdot 10^5$）—— 分别表示图中顶点的数量、边的数量以及查询的数量。

接下来的 $m$ 行描述图中的边，每行一条边。第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $c_i$（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$，$1 \leq c_i \leq 10^6$）—— 分别表示第 $i$ 条边的两个端点（从 $u_i$ 到 $v_i$）及其权重 $c_i$。

接下来的 $q$ 行描述查询，每行一个查询。第 $i$ 行若为第一类查询，则形如 $+\;v_i$；若为第二类查询，则形如 $-\;v_i$（$1 \leq v_i \leq n$）。

Output $q$ numbers. The $i$-th number is the cost of the graph after the first $i$ queries.

输出 $q$ 个数。其中第 $i$ 个数表示执行前 $i$ 次查询后图的代价。

In the first test:

• After the first query, it is most profitable to select the edges with numbers $3, 4, 5$, their total cost is $15$.
• After the second query, there are no highlighted vertices, which means that there are no suitable sets of edges, the cost of the graph is $-1$.
• After the third query, it is most profitable to select the edges with numbers $1, 2, 5$, their total cost is $14$.
• After the fourth query, it is most profitable to select the edges with numbers $4$ and $5$, their total cost is $12$.
• After the fifth query, it is most profitable to select only edge number $5$, its cost is $4$.
• After the sixth query, all vertices are highlighted and there is no need to select any edges, the cost of the graph is $0$.

在第一个测试用例中：

• 第一次查询后，选择编号为 $3, 4, 5$ 的边最为有利，它们的总代价为 $15$。
• 第二次查询后，没有高亮顶点，这意味着不存在满足条件的边集，图的代价为 $-1$。
• 第三次查询后，选择编号为 $1, 2, 5$ 的边最为有利，它们的总代价为 $14$。
• 第四次查询后，选择编号为 $4$ 和 $5$ 的边最为有利，它们的总代价为 $12$。
• 第五次查询后，仅选择编号为 $5$ 的边最为有利，其代价为 $4$。
• 第六次查询后，所有顶点均被高亮，因此无需选择任何边，图的代价为 $0$。