Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito quiere participar en la próxima carrera del Rally Paris-Tokio. Para esto quiere entrenar lo más posible.  Por lo que quiere encontrar en el mapa las dos ciudades que se encuentran lo más lejanas posibles.  El mapa cuenta con $N$ ciudades $(2 \le N \le 40000)$ numeradas del $1$ a $N$ y $M$ carreteras, estas pueden ser verticales u horizontales $(1 \le M \lt 40000)$ de diferentes tamaños $Z$ $(1 \le Z \le 1000)$. Cada ciudad está conectada a lo sumo con otras 4 ciudades con carreteras que pueden ir al Norte, Sur, Este y Oeste. Ninguna de las carreteras se cruzan y solamente existe un camino que una cualquier par de ciudades.

Input

La primera línea tiene dos números $N$ y $M$ separados por un espacio. Las siguientes $M$ líneas describen las carreteras. Por cada una de estas carreteras aparecen tres números ($A$, $B$ y $C$) y un carácter ($D$). Los dos primeros números ($A$ y $B$) son las ciudades que conecta la carretera, el tercer número ($C$) es la longitud de la carretera y el carácter ($D$ puede ser $N (norte)$, $S (sur)$, $E (este)$ o $W (oeste)$) es la dirección de la carretera que va de $A$ hacia $B$.

Output

En una línea se imprime la distancia entre las ciudades más alejadas.

Sample test(s)