## EZDIJKST - Easy Dijkstra Problem

Determine the shortest path between the specified vertices in the graph given in the input data.

Hint: You can use Dijkstra's algorithm.

Hint 2: if you're a lazy C++ programmer, you can use set and cin/cout (with sync_with_stdio(0)) - it should suffice.

### Input

first line - one integer - number of test cases

For each test case the numbers V, K (number of vertices, number of edges) are given,

Then K lines follow, each containing the following numbers separated by a single space:

a_{i}, b_{i}, c_{i}

It means that the graph being described contains an edge from a_{i} to b_{i},

with a weight of c_{i}.

Below the graph description a line containing a pair of integers A, B is present.

The goal is to find the shortest path from vertex A to vertex B.

All numbers in the input data are integers in the range 0..10000.

### Output

For each test case your program should output (in a separate line) a single number C - the length of the shortest path from vertex A to vertex B. In case there is no such path, your program should output a single word "NO" (without quotes)

### Example

Input:3 3 2 1 2 5 2 3 7 1 3 3 3 1 2 4 1 3 7 2 3 1 1 3 3 1 1 2 4 1 3Output:12 5 NO

Added by: | Robert Rychcicki |

Date: | 2009-01-10 |

Time limit: | 0.150s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS OBJC PERL6 VB.NET |