Shortest Path in Ninjaland

Ninjaland consists of ‘N’ states and ‘M’ paths. Each path connecting two states can either be a normal path or a special path, each with its unique length. Your task is to find the shortest distance between two given states such that the path includes at most one special path.

Example:

Input:

N = 3, M = 2
Paths = [[1, 2, 2, 3], [2, 3, 4, 2]]
X = 1, Y = 3

Output:

4

Explanation:

You can travel from state 1 to state 2 via the normal path (length 2) and from state 2 to state 3 via the special path (length 2), totaling 4.

Constraints:

• 1 <= T <= 10
• 1 <= N < 10³
• N-1 <= M <= 10³
• 1 <= A,B,X,Y <= N
• 1 <= W1,W2 <= 10⁶
• Time Limit: 1 sec

Note:

All paths are directed with no self-loops, and all states are inter-connected. Multiple paths can exist between two states, but at least one path will always exist between the two given states.