{"problem":{"name":"H. Hellcife is on fire","description":{"content":"The kingdom of Hellcife has several cities that are connected by some roads. One day, the king of Hellcife, Bair Jolsonaro, decided to set fire on some of these cities, just for fun. It's known that t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10244H"},"statements":[{"statement_type":"Markdown","content":"The kingdom of Hellcife has several cities that are connected by some roads. One day, the king of Hellcife, Bair Jolsonaro, decided to set fire on some of these cities, just for fun. It's known that the $i$-th city has a number $T_i$, indicating that if the fire reaches that city at time $X$, then at time $X + T_i$ this city will be completely burnt. After a city is completely burnt, the fire begins to spread across all the roads that are connected to this city, with speed of one meter per second. \n\nYour task is simple: you have to find, for each city, the amount of time it takes for the city to be completely burnt, knowing that at time 0 the king Bair Jolsonaro set fire on some cities.\n\nThe first line of input contains three numbers $N$, $M$ and $K$ ($1 <= N, M, K <= 10^5$), indicating the number of cities in Hellcife, the number of roads in Hellcife, and the number of cities Bair Jolsonaro initially set fire, respectively. \n\nEach of the following $M$ lines contains three integers $A_i$, $B_i$, and $C_i$ ($1 <= A_i, B_i <= N$, $A_i eq.not B_i$, $1 <= C_i <= 10^5$), indicating that there is a road between cities $A_i$ and $B_i$ with length of $C_i$ meters.\n\nThe next line of input contains $N$ numbers $T_i$ ($1 <= i <= N$, $1 <= T_i <= 10^5$).\n\nThe last line of the input contains $K$ numbers $X_i$ ($1 <= i <= K$, $1 <= X_i <= N$), indicating that the $X_i$-th city was chosen by Bair Jolsonaro to be set on fire in the beginning.\n\nThe output consists of $N$ lines, the $i$-th of them indicates the amount of time it takes for the $i$-th city to be completely burnt.\n\nIt is guaranteed that from any city you can reach any other city using some roads.\n\n## Input\n\nThe first line of input contains three numbers $N$, $M$ and $K$ ($1 <= N, M, K <= 10^5$), indicating the number of cities in Hellcife, the number of roads in Hellcife, and the number of cities Bair Jolsonaro initially set fire, respectively. Each of the following $M$ lines contains three integers $A_i$, $B_i$, and $C_i$ ($1 <= A_i, B_i <= N$, $A_i eq.not B_i$, $1 <= C_i <= 10^5$), indicating that there is a road between cities $A_i$ and $B_i$ with length of $C_i$ meters.The next line of input contains $N$ numbers $T_i$ ($1 <= i <= N$, $1 <= T_i <= 10^5$).The last line of the input contains $K$ numbers $X_i$ ($1 <= i <= K$, $1 <= X_i <= N$), indicating that the $X_i$-th city was chosen by Bair Jolsonaro to be set on fire in the beginning.\n\n## Output\n\nThe output consists of $N$ lines, the $i$-th of them indicates the amount of time it takes for the $i$-th city to be completely burnt.\n\n[samples]\n\n## Note\n\nIt is guaranteed that from any city you can reach any other city using some roads.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ N $ vertices (cities) and $ M $ edges (roads).  \nLet $ T_i \\in \\mathbb{Z}^+ $ denote the burn time of city $ i \\in V $.  \nLet $ C_{(u,v)} \\in \\mathbb{Z}^+ $ denote the length (in meters) of the road between cities $ u $ and $ v $.  \nLet $ S \\subseteq V $ be the set of initially ignited cities, with $ |S| = K $.  \n\n**Constraints**  \n1. $ 1 \\le N, M, K \\le 10^5 $  \n2. For each edge $ (u,v) \\in E $: $ 1 \\le C_{(u,v)} \\le 10^5 $  \n3. For each city $ i \\in V $: $ 1 \\le T_i \\le 10^5 $  \n4. $ S $ is given as a set of $ K $ distinct city indices.  \n5. $ G $ is connected.  \n\n**Objective**  \nFor each city $ i \\in V $, compute $ D_i \\in \\mathbb{R}^+ $, the time at which city $ i $ is completely burnt, defined recursively as:  \n- If $ i \\in S $, then $ D_i = T_i $ (fire is set at time 0, completes burning at $ T_i $).  \n- Otherwise, $ D_i = \\min_{(j,i) \\in E} \\left\\{ D_j + C_{(j,i)} \\right\\} + T_i $,  \n  where $ D_j $ is the time at which city $ j $ is completely burnt, and fire spreads from $ j $ to $ i $ along the road of length $ C_{(j,i)} $, taking $ C_{(j,i)} $ seconds to reach $ i $, then requiring $ T_i $ seconds to burn $ i $.  \n\nCompute $ D_i $ for all $ i \\in V $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10244H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}