{"problem":{"name":"D. Dynamic Shortest Path","description":{"content":"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_","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF843D"},"statements":[{"statement_type":"Markdown","content":"You are given a weighted directed graph, consisting of _n_ vertices and _m_ edges. You should answer _q_ queries of two types:\n\n*   _1 v_ — find the length of shortest path from vertex 1 to vertex _v_.\n*   _2 c _l_1 _l_2 ... _l__c__ — add 1 to weights of edges with indices _l_1, _l_2, ..., _l__c_.\n\n## Input\n\nThe 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.\n\nNext _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.\n\nNext _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\n## Output\n\nFor 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.\n\n[samples]\n\n## Note\n\n<center>The description of changes of the graph in the first sample case:\n\n![image](https://espresso.codeforces.com/15a1dd951fa6001d0dac06305baefc8389d34e53.png)\n\nThe description of changes of the graph in the second sample case:\n\n![image](https://espresso.codeforces.com/9fc8d601f62c2ab3b2dad3107b5398c5860eeb8b.png)\n\n</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个带权有向图，包含 #cf_span[n] 个顶点和 #cf_span[m] 条边。你需要回答 #cf_span[q] 个查询，分为两种类型：\n\n输入的第一行包含整数 #cf_span[n], #cf_span[m], #cf_span[q] (#cf_span[1 ≤ n, m ≤ 10^5], #cf_span[1 ≤ q ≤ 2000]) —— 分别表示图中的顶点数、边数和查询数。\n\n接下来的 #cf_span[m] 行描述了边：第 #cf_span[i] 行包含索引为 #cf_span[i] 的边的描述——三个整数 #cf_span[ai], #cf_span[bi], #cf_span[ci] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[0 ≤ ci ≤ 10^9])，分别表示边的起点、终点及其初始权重。\n\n接下来的 #cf_span[q] 行描述了查询，格式如上所述（#cf_span[1 ≤ v ≤ n], #cf_span[1 ≤ lj ≤ m]）。保证在单个查询中所有 #cf_span[lj] 互不相同。同时保证所有第二类查询中涉及的边总数不超过 #cf_span[10^6]。\n\n对于每个第一类查询，请在单独一行中输出从 #cf_span[1] 到 #cf_span[v] 的最短路径长度。如果不存在这样的路径，请输出 _-1_。\n\n第一个样例中图的变化描述：\n\n第二个样例中图的变化描述：\n\n## Input\n\n输入的第一行包含整数 #cf_span[n], #cf_span[m], #cf_span[q] (#cf_span[1 ≤ n, m ≤ 10^5], #cf_span[1 ≤ q ≤ 2000]) —— 分别表示图中的顶点数、边数和查询数。接下来的 #cf_span[m] 行描述了边：第 #cf_span[i] 行包含索引为 #cf_span[i] 的边的描述——三个整数 #cf_span[ai], #cf_span[bi], #cf_span[ci] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[0 ≤ ci ≤ 10^9])，分别表示边的起点、终点及其初始权重。接下来的 #cf_span[q] 行描述了查询，格式如上所述（#cf_span[1 ≤ v ≤ n], #cf_span[1 ≤ lj ≤ m]）。保证在单个查询中所有 #cf_span[lj] 互不相同。同时保证所有第二类查询中涉及的边总数不超过 #cf_span[10^6]。\n\n## Output\n\n对于每个第一类查询，请在单独一行中输出从 #cf_span[1] 到 #cf_span[v] 的最短路径长度。如果不存在这样的路径，请输出 _-1_。\n\n[samples]\n\n## Note\n\n第一个样例中图的变化描述：\n\n第二个样例中图的变化描述：","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a weighted directed graph, where:  \n- $ V = \\{1, 2, \\dots, n\\} $ is the set of vertices.  \n- $ E = \\{e_1, e_2, \\dots, e_m\\} $ is the set of directed edges, where each edge $ e_i = (a_i, b_i, c_i) $ has source $ a_i \\in V $, target $ b_i \\in V $, and initial weight $ c_i \\in \\mathbb{R}_{\\geq 0} $.  \n\nLet $ Q $ be a sequence of $ q $ queries, each of one of two types:  \n- **Type 1**: Given $ v \\in V $, compute the shortest path distance from vertex $ 1 $ to vertex $ v $.  \n- **Type 2**: Given $ v \\in V $ and a set $ L = \\{l_1, l_2, \\dots, l_k\\} \\subseteq \\{1, 2, \\dots, m\\} $ of distinct edge indices, update the weight of each edge $ e_{l_j} $ to $ 0 $.  \n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 10^5 $  \n2. $ 1 \\leq q \\leq 2000 $  \n3. For each edge $ e_i = (a_i, b_i, c_i) $: $ 1 \\leq a_i, b_i \\leq n $, $ 0 \\leq c_i \\leq 10^9 $  \n4. For each Type 2 query:  \n   - All $ l_j \\in L $ are distinct.  \n   - Total number of edges updated across all Type 2 queries $ \\leq 10^6 $  \n\n**Objective**  \nFor each Type 1 query with parameter $ v $, compute:  \n$$\nd(v) = \\min \\left\\{ \\sum_{e \\in P} w(e) \\,\\middle|\\, P \\text{ is a path from } 1 \\text{ to } v \\right\\}\n$$  \nwhere $ w(e) $ is the current weight of edge $ e $ (initial or updated).  \nIf no such path exists, output $ -1 $.  \n\nFor each Type 2 query, update:  \n$$\nw(e_{l_j}) \\leftarrow 0 \\quad \\forall l_j \\in L\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF843D","tags":["graphs","shortest paths"],"sample_group":[["3 2 9\n1 2 0\n2 3 0\n2 1 2\n1 3\n1 2\n2 1 1\n1 3\n1 2\n2 2 1 2\n1 3\n1 2","1\n0\n2\n1\n4\n2"],["5 4 9\n2 3 1\n2 4 1\n3 4 1\n1 2 0\n1 5\n1 4\n2 1 2\n2 1 2\n1 4\n2 2 1 3\n1 4\n2 1 4\n1 4","\\-1\n1\n2\n3\n4"]],"created_at":"2026-03-03 11:00:39"}}