Oil Trails

Mike owns many houses. Every morning he wakes up in one of them, drives back and forth between his houses until he is tired, and goes to bed in whichever house he stopped at. Oil leaks from his car, so each drive from one house to another leaves one oil trail between those two houses.

Servants live in Mike's houses, and they sometimes drive between the houses as well. Their cars leak oil too, so at the end of the day the trails alone do not say who left them.

Neither Mike nor a servant ever returns to the house they left without visiting a different house first, so no trail joins a house to itself. Driving the same pair of houses twice leaves two trails.

You are given the number of houses at the end of one day and the number of oil trails between each pair of houses. Decide whether, based only on this information, it is possible that Mike left every trail himself.

The first line contains the number of test cases $T$ ($1 \le T \le 1000$).

Each test case is given on two lines. The first line contains the number of houses $n$ ($2 \le n \le 100$), numbered $0$ through $n-1$. The second line begins with the number of triples $k$ ($0 \le k \le n(n-1)/2$), followed by $k$ triples. A triple $x\ y\ z$ means there are $z$ oil trails between house $x$ and house $y$ ($0 \le x, y \le n-1$, $x \ne y$, $1 \le z \le 5$). Trails have no direction, so if the triple $x\ y\ z$ occurs then $y\ x\ z$ is assumed to exist but does not appear in the input. Each pair of houses appears in at most one triple, and a pair that appears in no triple has no trails between it.

For each test case print yes on its own line if Mike could have left every oil trail himself, and no otherwise.