Question:

Given a weighted, directed graph with n nodes and medges, where each edge has an associated weight $($both positive and negative$),$ design an algorithm to determine if there is a negative weight cycle reachable from a specified starting node s$.$

A negative weight cycle is a cycle in the graph where the sum of the edge weights is negative. The algorithm should return True if such a cycle exists and False otherwise.

Provide a Python implementation and explain the approach in detail, including time complexity.

Constraints:

The graph has n nodes and m edges.

Edge weights range from $-10^3$ to ${10}^3.$

Function Signature:

Python

Copy code

def has$\_$negative$\_$cycle$($n: int,

edges: List$[$Tuple$[$int$,$ int, int$]],$

s: int$)->$ bool:

# Your code here

Example:

Input:

Copy codeOutput: True $($There is a negative cycle:

$1231$