Explorando sus muchas granjas, el Granjero Juan (GJ) ha descubierto un número de agujeros de lombrices asombrosos. ¡Un agujero de lombriz es muy peculiar debido a que es un camino de una vía que lo lleva a usted a su destino en un tiempo que es ANTERIOR al que era cuando usted entró al agujero de lombriz! Cada una de las granjas de GJ abarca ~N (1 \leq N \leq 500)~ campos convenientemente numerados ~1..N~, ~M (1 \leq M \leq 2500)~ caminos, y ~W (1 \leq W \leq 200)~ agujeros de lombrices.

Como GJ es un admirador ávido de viajes en el tiempo, él quiere hacer lo siguiente: comenzar en algún campo, viajar a través de algunos caminos y agujeros de lombrices, y volver al campo inicial antes de su partida inicial. Tal vez él será capaz de encontrarse a sí mismo :).

Para ayudar a GJ a averiguar si esto es posible o no, él le dará a usted un mapa completo de ~F (1 \leq F \leq 5)~ de sus granjas. Ningún camino necesitará más de ~10,0000~ segundos para ser recorrido y ningún hueco de lombriz podrá devolver en el tiempo a GJ en más de ~10,000~ segundos.

Entrada

• Línea 1: Un solo entero ~F~. Siguen ~F~ descripciones de granjas.

• Línea 1 de cada granja: Tres enteros separados por espacios, respectivamente: ~N, M,~ y ~W~.

• Líneas 2..M+1 de cada granja: Tres enteros separados por espacios ~(S, E, T)~ que describen, respectivamente: un camino bidireccional entre ~S~ y ~E~ que requiere ~T~ unidades de tiempo para recorrerse. Dos campos podrían estar conectados por más de un camino.

• Líneas M+2..M+W+1 de cada granja: Tres enteros separados por espacios ~(S, E, T)~ que describen, respectivamente: un camino de una sola vía de ~S~ a ~E~ que también devuelve al viajero ~T~ unidades de tiempo en el tiempo.

Salida

• Líneas 1..F: Para cada granja, dé como salida "~YES~" si GJ puede lograr su objetivo, en caso contrario dé como salida "~NO~" (no incluya las comillas).

Ejemplo de Entrada

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Detalles de la Entrada: Dos mapas de granjas. La primera tiene tres caminos y un agujero de lombriz, y la segunda tiene dos caminos y un hueco de lombriz.

Ejemplo de Salida

NO
YES