Can any shortest$-$path from to any vertex in the extended constrains graph be positive? Explain your analysis. $(20$ points $)$

Bellman$-$Ford Algorithm $(30$ points $)$

You are given a directed graph with $\text{'}$ N $\text{'}$ vertices and $\text{'}M\text{'}$ edges, where each edge has a weight $($which can be positive or negative$).$ The graph represents a network where vertices are nodes and edges are the connections between them, with the weights representing the cost of traversing from one node to another.

Given a starting node $`$S$\text{'},$ your task is to determine the shortest path from the starting node $\text{'}$S$\text{'}$ to all other nodes in the graph using the Bellman$-$Ford algorithm. Additionally, you need to identify if there are any negative weight cycles in the graph.

Input:

An integer $\text{'}N\text{'}$ representing the number of vertices.

An integer $`M\text{'}$ representing the number of edges.

graph using the Bellman$-$Ford algorithm.

Additionally, you need to identify if there are any negative weight cycles in the graph.

Input:

An integer $\text{'}$ N $\text{'}$ representing the number of vertices.

An integer representing the number of edges.

A list of edges, each defined by three integers: u $v$ w$`$ is the weight of the edge.

An integer representing the starting node.

Output:

A list of shortest distances from the starting node $`$S$\text{'}$ to each of the other nodes. If a node is unreachable, indicate it with an appropriate value $($e$.$g$.,$ "Infinity"$).$

A statement indicating whether or not there is a negative weight cycle in the graph.