CF843D.Dynamic Shortest Path

You are given a weighted directed graph, consisting of n vertices and m edges. You should answer q queries of two types:

• 1 v — find the length of shortest path from vertex 1 to vertex v.
• 2 c _l_1 _l_2 ... l__c — add 1 to weights of edges with indices _l_1, _l_2, ..., l__c.

给你一个带权有向图，包含 $n$ 个顶点和 $m$ 条边。你需要回答 $q$ 个查询，查询分为两类：

• 1 v — 求从顶点 $1$ 到顶点 $v$ 的最短路径长度；
• 2 c l_1 l_2 ... l_c — 将编号为 $l_1,\,l_2,\,...,\,l_c$ 的边的权重各加 $1$。

The first line of input data contains integers n, m, q (1 ≤ n, m ≤ 105, 1 ≤ q ≤ 2000) — the number of vertices and edges in the graph, and the number of requests correspondingly.

Next m lines of input data contain the descriptions of edges: i-th of them contains description of edge with index i — three integers a__i, b__i, c__i (1 ≤ a__i, b__i ≤ n, 0 ≤ c__i ≤ 109) — the beginning and the end of edge, and its initial weight correspondingly.

Next q lines of input data contain the description of edges in the format described above (1 ≤ v ≤ n, 1 ≤ l__j ≤ m). It's guaranteed that inside single query all l__j are distinct. Also, it's guaranteed that a total number of edges in all requests of the second type does not exceed 106.

输入数据的第一行包含整数 $n$、$m$、$q$（$1 ≤ n, m ≤ 10^5$，$1 ≤ q ≤ 2000$），分别表示图中顶点数、边数以及查询次数。

接下来的 $m$ 行输入数据描述各条边：其中第 $i$ 行描述编号为 $i$ 的边——包含三个整数 $a_i$、$b_i$、$c_i$（$1 ≤ a_i, b_i ≤ n$，$0 ≤ c_i ≤ 10^9$），分别表示该边的起点、终点及其初始权重。

接下来的 $q$ 行输入数据描述边的查询，格式同上（$1 ≤ v ≤ n$，$1 ≤ l_j ≤ m$）。保证在单个查询中所有 $l_j$ 互不相同。同时保证所有第二类查询中涉及的边的总数不超过 $10^6$。

For each query of first type print the length of the shortest path from 1 to v in a separate line. Print -1, if such path does not exists.

对于每个第一类查询，在单独一行中输出从节点 1 到节点 $v$ 的最短路径长度。如果这样的路径不存在，则输出 $-1$。

The description of changes of the graph in the first sample case:

The description of changes of the graph in the second sample case:

第一个样例中图的变化描述：

第二个样例中图的变化描述：