{"raw_statement":[{"iden":"statement","content":"You are given an undirected connected weighted graph that is comprised of a chain that connects simple cycles. No two cycles in the graph share a common vertex, therefore you can imagine the graph as circles of nodes connected by chains. Assuming size n, the nodes 1 and n are guaranteed to *not* be on cycles and have a degree of size one, and *all nodes of the graph are on a simple path from node 1 to node n*.\n\nYou want to travel from node 1 to node n and back to node 1 in minimal time. At any node along the way from node 1 to n, when you are at node u, you can assign it as one end of a magical portal. But once you assign it, you have no more than k seconds to assign the other end of the portal v, otherwise it will disappear. Once you assign the two ends, the portal is activated and you may use it to travel between node u and v in zero time.\n\nAssuming you travel and choose the portal ends optimally, what is the minimal time needed to get from node 1 to node n and back to node 1 using at most one portal?\n\nThe first line of input contains three integers n, e, k (2 ≤ n ≤ 3 × 105, e ≥ n - 1, 1 ≤ k ≤ 108), the number of nodes, edges, and k is the timeout after first portal end is assigned.\n\nEach of the following e lines contains three integers u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 1000), representing that nodes u and v are connected by an edge that takes w seconds to cross.\n\nIt is guaranteed that there are no loops or multiple edges and that the graph is connected, with nodes 1 and n having degree one.\n\nThe given graph matches the description in the problem statement.\n\nOn a single line, output the minimal time needed to get from node 1 to node n and back to node 1 using at most one portal.\n\nThe sample test is illustrated in the picture above. To minimize the time, we start at node 1 move to node 5 in 5 seconds, assign it as the first end of the portal, then move to node 12 in 14 seconds, and assign it as the other end of the portal, then we can go back from node 12 to node 5 in *zero* seconds using the portal, then move to node 1 in 5 seconds. So the total time would be 5+14+0+5=24.\n\nAs the travelling distance between the two ends of the portal doesn't exceed k = 14, our solution is valid.\n\n"},{"iden":"input","content":"The first line of input contains three integers n, e, k (2 ≤ n ≤ 3 × 105, e ≥ n - 1, 1 ≤ k ≤ 108), the number of nodes, edges, and k is the timeout after first portal end is assigned.Each of the following e lines contains three integers u, v, w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 1000), representing that nodes u and v are connected by an edge that takes w seconds to cross.It is guaranteed that there are no loops or multiple edges and that the graph is connected, with nodes 1 and n having degree one.The given graph matches the description in the problem statement."},{"iden":"output","content":"On a single line, output the minimal time needed to get from node 1 to node n and back to node 1 using at most one portal."},{"iden":"note","content":"The sample test is illustrated in the picture above. To minimize the time, we start at node 1 move to node 5 in 5 seconds, assign it as the first end of the portal, then move to node 12 in 14 seconds, and assign it as the other end of the portal, then we can go back from node 12 to node 5 in *zero* seconds using the portal, then move to node 1 in 5 seconds. So the total time would be 5+14+0+5=24.As the travelling distance between the two ends of the portal doesn't exceed k = 14, our solution is valid."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected connected weighted graph with $ |V| = n $, $ |E| = e $, where:  \n- $ V = \\{1, 2, \\dots, n\\} $,  \n- Each edge $ (u, v) \\in E $ has weight $ w(u, v) \\in \\mathbb{Z}^+ $,  \n- The graph is a *chain of simple cycles*: a path from node $ 1 $ to node $ n $, with disjoint simple cycles attached to intermediate nodes on this path,  \n- Nodes $ 1 $ and $ n $ have degree 1 and are not part of any cycle,  \n- All nodes lie on the unique simple path from $ 1 $ to $ n $ (i.e., the graph is a *cactus* with exactly one path between $ 1 $ and $ n $, and cycles are pendant).  \n\nLet $ P = (v_0 = 1, v_1, \\dots, v_m = n) $ be the unique simple path from $ 1 $ to $ n $, where $ m \\leq n $.  \nLet $ d(i, j) $ denote the shortest distance (sum of edge weights) between nodes $ i $ and $ j $ along the graph.  \n\nLet $ k \\in \\mathbb{Z}^+ $ be the portal timeout: once one end is placed at node $ u $, the other end $ v $ must be placed within $ k $ seconds of travel time from $ u $, i.e., $ d(u, v) \\leq k $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 3 \\times 10^5 $  \n2. $ e \\geq n - 1 $  \n3. $ 1 \\leq k \\leq 10^8 $  \n4. All edge weights $ w \\in [1, 1000] $  \n5. Graph is connected, no multiple edges or self-loops  \n6. Nodes $ 1 $ and $ n $ have degree 1, and all nodes lie on the unique $ 1 $–$ n $ path  \n\n**Objective**  \nCompute the minimal total time to travel from node $ 1 $ to node $ n $ and back to node $ 1 $, using **at most one portal**.  \n\nWithout portal, the cost is $ 2 \\cdot d(1, n) $.  \n\nWith one portal:  \n- Choose nodes $ u $ and $ v $ such that $ d(u, v) \\leq k $,  \n- Travel path: $ 1 \\to u \\to v \\to n \\to v \\to u \\to 1 $,  \n- Total time: $ d(1, u) + d(u, v) + d(v, n) + d(n, v) + d(v, u) + d(u, 1) $,  \n- But portal allows $ d(u, v) = 0 $, so:  \n  $$\n  T = d(1, u) + d(u, v) + d(v, n) + d(n, v) + d(v, u) + d(u, 1) - 2 \\cdot d(u, v)\n  $$  \n  Simplifies to:  \n  $$\n  T = 2 \\cdot d(1, u) + 2 \\cdot d(v, n)\n  $$  \n  since $ d(u, v) \\leq k $, and portal cancels both $ d(u,v) $ and $ d(v,u) $.  \n\nBut note: path is $ 1 \\to u \\to v \\to n $, then $ n \\to v \\to u \\to 1 $, so:  \n- Forward: $ d(1, u) + d(u, v) + d(v, n) $  \n- Backward: $ d(n, v) + d(v, u) + d(u, 1) $  \n- With portal: $ d(u, v) = d(v, u) = 0 $, so total:  \n  $$\n  T = d(1, u) + d(v, n) + d(n, v) + d(u, 1) = 2 \\cdot d(1, u) + 2 \\cdot d(v, n)\n  $$  \n\nThus, minimize:  \n$$\n\\min_{\\substack{u, v \\in V \\\\ d(u, v) \\leq k}} \\left( 2 \\cdot d(1, u) + 2 \\cdot d(v, n) \\right)\n$$  \n\nSubject to $ d(u, v) \\leq k $.  \n\nEquivalently:  \n$$\n\\min_{\\substack{u, v \\in V \\\\ d(u, v) \\leq k}} \\left( 2 \\cdot (d(1, u) + d(v, n)) \\right)\n$$  \n\nAnd final answer is:  \n$$\n\\min\\left( 2 \\cdot d(1, n), \\min_{\\substack{u, v \\in V \\\\ d(u, v) \\leq k}} 2 \\cdot (d(1, u) + d(v, n)) \\right)\n$$","simple_statement":"You are given a connected graph shaped like a chain of cycles (no shared vertices between cycles), with nodes 1 and n being endpoints (degree 1). You must go from node 1 to node n and back to node 1. You can use at most one portal: choose two nodes u and v, spend at most k seconds to travel from u to v after setting u as the first end, then teleport for free between u and v. Find the minimum total travel time.","has_page_source":false}