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*.
You 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.
Assuming 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?
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.
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.
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.
## Input
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.
## Output
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.
[samples]
## Note
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.
**Definitions**
Let $ G = (V, E) $ be an undirected connected weighted graph with $ |V| = n $, $ |E| = e $, where:
- $ V = \{1, 2, \dots, n\} $,
- Each edge $ (u, v) \in E $ has weight $ w(u, v) \in \mathbb{Z}^+ $,
- 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,
- Nodes $ 1 $ and $ n $ have degree 1 and are not part of any cycle,
- 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).
Let $ P = (v_0 = 1, v_1, \dots, v_m = n) $ be the unique simple path from $ 1 $ to $ n $, where $ m \leq n $.
Let $ d(i, j) $ denote the shortest distance (sum of edge weights) between nodes $ i $ and $ j $ along the graph.
Let $ 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 $.
**Constraints**
1. $ 2 \leq n \leq 3 \times 10^5 $
2. $ e \geq n - 1 $
3. $ 1 \leq k \leq 10^8 $
4. All edge weights $ w \in [1, 1000] $
5. Graph is connected, no multiple edges or self-loops
6. Nodes $ 1 $ and $ n $ have degree 1, and all nodes lie on the unique $ 1 $–$ n $ path
**Objective**
Compute the minimal total time to travel from node $ 1 $ to node $ n $ and back to node $ 1 $, using **at most one portal**.
Without portal, the cost is $ 2 \cdot d(1, n) $.
With one portal:
- Choose nodes $ u $ and $ v $ such that $ d(u, v) \leq k $,
- Travel path: $ 1 \to u \to v \to n \to v \to u \to 1 $,
- Total time: $ d(1, u) + d(u, v) + d(v, n) + d(n, v) + d(v, u) + d(u, 1) $,
- But portal allows $ d(u, v) = 0 $, so:
$$
T = d(1, u) + d(u, v) + d(v, n) + d(n, v) + d(v, u) + d(u, 1) - 2 \cdot d(u, v)
$$
Simplifies to:
$$
T = 2 \cdot d(1, u) + 2 \cdot d(v, n)
$$
since $ d(u, v) \leq k $, and portal cancels both $ d(u,v) $ and $ d(v,u) $.
But note: path is $ 1 \to u \to v \to n $, then $ n \to v \to u \to 1 $, so:
- Forward: $ d(1, u) + d(u, v) + d(v, n) $
- Backward: $ d(n, v) + d(v, u) + d(u, 1) $
- With portal: $ d(u, v) = d(v, u) = 0 $, so total:
$$
T = d(1, u) + d(v, n) + d(n, v) + d(u, 1) = 2 \cdot d(1, u) + 2 \cdot d(v, n)
$$
Thus, minimize:
$$
\min_{\substack{u, v \in V \\ d(u, v) \leq k}} \left( 2 \cdot d(1, u) + 2 \cdot d(v, n) \right)
$$
Subject to $ d(u, v) \leq k $.
Equivalently:
$$
\min_{\substack{u, v \in V \\ d(u, v) \leq k}} \left( 2 \cdot (d(1, u) + d(v, n)) \right)
$$
And final answer is:
$$
\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)
$$