给定一个带权有向图,由 n 个顶点和 m 个边组成。您应该回答 q 两种类型的查询:
- 1 v — 求从顶点 1 到顶点 v 的最短路径的长度。
- 2 c l1 l2 ... lc - 将索引为 l1, l2, ..., lc 的边的权重加 1。
输入
输入数据的第一行包含整数 n、m、q (1 ≤ n, m ≤ 105, 1 ≤ q ≤ 2000) — 图中的顶点和边的数量,以及相应的请求数量。
接下来 m 行输入数据包含边的描述:其中第 i 行包含索引为 i 的边的描述 — 三个整数 ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109) — 边的开始和结束,以及相应的初始权重。
接下来 q 行输入数据包含上述格式的边描述 (1 ≤ v ≤ n, 1 ≤ lj ≤ m)。保证在单个查询内所有 lj 都是不同的。并且保证第二类所有请求的边总数不超过106。
输出
对于第一种类型的每个查询,在单独的行中打印从 1 到 v 的最短路径的长度。如果这样的路径不存在,则打印 -1。
示例
输入 #1
3 2 9 1 2 0 2 3 0 2 1 2 1 3 1 2 2 1 1 1 3 1 2 2 2 1 2 1 3 1 2
输出 #1
1 0 2 1 4 2
输入 #2
5 4 9 2 3 1 2 4 1 3 4 1 1 2 0 1 5 1 4 2 1 2 2 1 2 1 4 2 2 1 3 1 4 2 1 4 1 4
输出 #2
-1 1 2 3 4
注意
第一个样例中图形的变化描述:第二个样例中图形的变化描述: