Minimum Walk Cost With Free Repeated Edges

You are given an undirected weighted graph with n nodes numbered 0 to n - 1, and a list edges where edges[i] = [u, v, w] is an edge between nodes u and v with weight w. You are also given three nodes start, via, and target.

You walk from start to via, and then from via to target. The walk moves along edges and may visit any node or use any edge more than once.

The first time the walk uses an edge, you pay its weight w. Every later use of the same edge, in either direction, is free.

Return the minimum total amount you have to pay. If via or target can't be reached from start, return -1.

Note that start, via, and target don't have to be different nodes. Two parallel edges between the same pair of nodes are different edges, so each is paid for separately if both are used.

Examples

Example 1

Input:  n      = 4
        edges  = [[0, 1, 4],
                  [1, 2, 4],
                  [1, 3, 1],
                  [3, 2, 1],
                  [0, 3, 6]]
        start  = 0
        via    = 3
        target = 2
Output: 6
Explanation: Walk 0 -> 1 -> 3 -> 2 and pay 4 + 1 + 1 = 6. Taking the direct edge from 0 to 3 instead costs 6 on its own, and reaching 2 afterwards adds 1 more.

Example 2

Input:  n      = 5
        edges  = [[0, 1, 2],
                  [1, 2, 2],
                  [1, 3, 3]]
        start  = 0
        via    = 2
        target = 3
Output: 7
Explanation: Walk 0 -> 1 -> 2 -> 1 -> 3. The edge between 1 and 2 is used twice but paid once, so the total is 2 + 2 + 3 = 7. Paying for the shortest route from 0 to 2 and then the shortest route from 2 to 3 separately would cost 4 + 5 = 9.

Example 3

Input:  n      = 4
        edges  = [[0, 1, 1]]
        start  = 0
        via    = 1
        target = 3
Output: -1
Explanation: Node 3 has no edges, so it can't be reached from node 0.