Description
Given a directed graph G = (V,E) with edge length l(e) and a source vertex s. Find out if there is a negative cycle in G. A negative cycle in a graph is a cycle with negative length.
# Input
The graph has `n` vertices and `m` edges.
There are m + 1 lines, the first line gives three numbers `n`,`m` and `s`(1 <= s <=n), describing the number of vertices, the number of edges and the source vertex. Each of the following lines contains three integers `a`, `b` and `c`, meaning there is an edge (a,b) belong to E and the length of the edge is c. All the numbers in a line are separated by space. (`1 <= a,b <= n`)
1 <= `n` <= 1000, 1 <= `m` <= 5000, and the length of `edge` is in the range of [-1000, 1000]. You can assume that all the vertices are reachable from `s`.
Your code should read the input from standard input (e.g.
using functions `input()/raw_input()` in Python and `cin/scanf` in C++).
# Output
One line, if there is a negative cycle, output should be ‘True’. If not, output should be ‘False’.
Your code should write the output to standard output (e.g. using functions `print` in Python and `cout/printf` in C++).
