405960: GYM102191 K Cactus Portal

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 × 10⁵, e ≥ n - 1, 1 ≤ k ≤ 10⁸), 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.

12 13 14
1 2 2
4 3 5
10 9 2
9 8 7
2 5 3
6 4 2
2 3 2
10 11 5
11 7 6
9 12 4
5 4 3
8 7 1
10 6 3

24

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.