Cheapest Path With a Free Node

You are given an undirected graph with n nodes numbered 0 to n - 1, an edge list edges where edges[i] = [u, v] connects nodes u and v, and an array cost where cost[i] is the price of visiting node i.

The price of a path is the sum of cost over every node on it, including the first and the last.

You may optionally designate exactly one node on the path as free: that node contributes 0 instead of its cost, but the node visited immediately after it on the path contributes twice its cost. If the free node is the last node of the path, there is no next node, so no penalty applies. All other nodes are priced normally.

Return the minimum price of a path from start to target. If target cannot be reached from start, return -1. If start == target, the answer is 0, since the only node on the path can be made free.

Examples

Example 1

Input: n = 4, edges = [[0,1],[1,2],[2,3]], cost = [1,100,1,1], start = 0, target = 3
Output: 4
Explanation: Make node 1 free: 1 + 0 + 2*1 + 1 = 4. Without the free node the path costs 103.

Example 2

Input: n = 3, edges = [[0,1],[1,2]], cost = [5,5,5], start = 0, target = 2
Output: 10
Explanation: Make the last node free: 5 + 5 + 0 = 10. Freeing an earlier node doubles the next one and gains nothing.

Example 3

Input: n = 2, edges = [], cost = [1,1], start = 0, target = 1
Output: -1
Explanation: Node 1 is unreachable.