Valley of Peace is not only famous for Inner Peace but also well known for the delicious pizzas of Mr. Ping, the goose father of legendary Kung Fu Panda Po.

The delicious pizza of Mr. Ping has become so much famous that the demand of it has increased to a great extent. Mr. Ping wants to deliver his pizzas to Gongmen City which is ruled by Evil Lord Shen. Wolf bandits are guarding the Gongmen City and everywhere else. So, there are some fixed allowable amounts of pizza C_k that can be carried through k^th road. For some reason, the roads are one way only. Assume that there are N cities, Valley of Peace is the 1^st city and Gongmen City is the N^th city.

Mr. Ping along with Master Shifu has calculated the demands for each city and a least amount of pizzas L_k (≤ C_k) for k^th road that must be sent to satisfy the demands. Mr. Ping always wanted Po to become a great chef like him but Panda Po was busy practicing Kung Fu. So, now Mr. Ping has given him the job to deliver pizzas to Gongmen City fulfilling the requirements stated above.

Po along with his team cannot carry more or not even less than allowable amount assigned for each road, otherwise Stealth Mode will be broken and they will get caught. If the amount of pizzas going through the road from i^th city to j^th (1 < i, j < N) city is F_ij, then for each i, the following condition must hold:

$$\sum_{i=1}^N F_{ij} = \sum_{i=1}^N F_{ji}$$

Po is very excited to complete this awesome task along with Thundering Rhino and all helping hands possible. As you are a good friend of Panda; he wanted your help to know if it is possible to get this job done.

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers N (2 ≤ N ≤ 200) and M where N denotes the number of cities and M denotes the number of unidirectional roads. The k^th line of the next M lines contains four integers u_k v_k L_k C_k (1 ≤ u_k < N and 1 < v_k ≤ N, u_k ≠ v_k, 0 ≤ L_k ≤ C_k ≤ 10⁵) meaning that there is a road from city u_k to v_k, and at least L_k units of pizza must be sent through this road but not exceeding C_k units. There can be at most one road from a city u to v and from any city u, it's impossible to return to u visiting other cities.

For each case, print the case number and yes if it's possible to deliver the pizzas maintaining the restrictions, or no otherwise. If it's possible to do so, print extra M lines, where the k^th line should contain the amount of pizza that should be sent through the k^th road. There can be multiple solutions, report any valid one.

• Dataset is huge, use faster I/O methods.
• This is a special judge problem; wrong output format may cause 'Wrong Answer'.