Back

Euclidean Space

Worth 8 point(s) - Runtime Limit: 1 seconds

Introduction

Euclid, known as the father of geometry, was a Greek mathematician who lived over 2000 years ago. Back then, all geometers had were circle compasses and straight-edges. This limited most of geometry to a 2D plane. This branch of geometry is called, unsurprisingly, Euclidean geometry. Of course, since then, geometry has ascended to 3D space, 4D space, and even to a space in which the number of dimensions is recursively defined (thanks, Ron Graham). All of these higher dimensional spaces are considered Euclidean spaces if the axioms laid down in Euclidean geometry still hold true. One such axiom is that the distance between two points is always less than or equal to the distance from the first point to any set of intermediate points to the last point. In other words, the shortest distance between two points is a straight line. If this is not true, then we can conclude that the points are not in Euclidean space.

Input:
The first line of input contains an integer D, the number of test cases. Each test case starts with a single line containing an integer N, the number of points which are in question, and an integer Q, the number of distances given. Points in a space are numbered 1, 2, 3,...N. The next Q lines each 3 integers p1, p2, and d, respectively, where p1 ≠ p2, denoting that the distance between points p1 and p2 is d.

Output:
For each test case, output a line containing “Yes” if the space is possibly Euclidean space or “No” if the space cannot be Euclidean space.

Sample Input

2
3 3
1 2 11
2 3 5
1 3 7
4 4
1 2 13
2 3 3
3 4 2
1 4 4

Sample Output

Yes
No