PROGRAMMING:The shortest path of negative loop
Given a digraph which may contain negative weight edges, the shortest path length between any two vertices can be obtained. However, if the graph contains rings with negative weight sum, as shown in Figure 1, the shortest path between some vertices becomes meaningless, because the distance becomes shorter every time you walk in the negative ring. Please write a program to find the shortest path length between any two vertices. If the graph contains a negative weight ring, the program can also recognize it. Suppose that the graph contains n vertices, numbered from 0 to n-1.
###Input format:
**The input contains multiple groups of data * *, the first line of each group of data is three positive integers, N, e, m, N and E are the number of vertices and edges of the graph respectively, all of which are not more than 100. Next, line e represents the information of each edge, and each line has three integers a, B, and C, where a and B represent the endpoint number of the edge, and C represents the weight. The sides are not arranged in end numbered order. Next, M rows represent m groups of queries, and each row contains two integers x and y, representing two vertex numbers.
Tip: EOF can be used to judge the end of input
###Output format:
For each group of data, if there is a negative weight ring in the graph, only "negative circle" will be output. If there is no negative weight ring in the graph, M rows will be output. The shortest path length from vertex x to vertex y in each row will be output. If x and Y are not connected, then "None" will be output.
###Input example:
```in
4 3 2
0 1 1
1 2 1
0 3 1
0 2
3 2
2 2 2
0 1 1
1 0 -2
0 1
1 0
```
###Output example:
```out
two
none
negative circle
```
answer：If there is no answer, please comment
###Input format:
**The input contains multiple groups of data * *, the first line of each group of data is three positive integers, N, e, m, N and E are the number of vertices and edges of the graph respectively, all of which are not more than 100. Next, line e represents the information of each edge, and each line has three integers a, B, and C, where a and B represent the endpoint number of the edge, and C represents the weight. The sides are not arranged in end numbered order. Next, M rows represent m groups of queries, and each row contains two integers x and y, representing two vertex numbers.
Tip: EOF can be used to judge the end of input
###Output format:
For each group of data, if there is a negative weight ring in the graph, only "negative circle" will be output. If there is no negative weight ring in the graph, M rows will be output. The shortest path length from vertex x to vertex y in each row will be output. If x and Y are not connected, then "None" will be output.
###Input example:
```in
4 3 2
0 1 1
1 2 1
0 3 1
0 2
3 2
2 2 2
0 1 1
1 0 -2
0 1
1 0
```
###Output example:
```out
two
none
negative circle
```
answer：If there is no answer, please comment