Problem $3($Detecting Negative$-$Weight Cycles, $15$ points$)$

In lecture we mentioned why it does not make sense to consider shortest paths on a graph

with negative$-$weight cycles, but how do we detect if a graph contains such a cycle? Recall

that a negative$-$weight cycle is defined as a cycle where the sum of the weights of the edges

in the cycle is negative. Show how one can use the output of the Floyd$-$Warshall algorithm

to detect the presence of a negative$-$weight cycle in a directed graph. Briefly argue the

correctness of your algorithm.