当前没有测试数据。

Construction Schedule

There are many tasks which need to be done in order to construct a building. In order to perform these tasks, there should be a reasonable schedule. There might be relations between tasks. The difficulty we meet in creating a schedule is that the schedule has to satisfy all given relations among the given tasks.

Given a set of tasks and their relations, your task is to write a program to check whether it is possible to create a schedule to perform the tasks.

Input 

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains two integer numbers n (1n500), and k (0k20000) separated by spaces, where n denotes the total number of tasks, and k denotes the total number of relations. The next k following lines describe k relations among the tasks. Let t_j be a starting time of the task j, j = 1, 2,..., n. Each relation is in one of the two forms:

• x y v means task x must not start after task y starts v days, i.e. t_xt_y + v,

• x y  - v means task x must not start before task y starts v days, i.e. t_xt_y + v, where v is a positive integer not greater than 10 000.

Output 

For each test case, write in one line ``YES" if it is possible to construct a schedule to satisfy all the given relations among the given tasks, ``NO" otherwise.

Sample Input 

2 
2 2 
1 2 -2 
1 2 1 
2 1 
1 2 -1

Sample Output 

NO 
YES