Una red tiene \(n\) nodos, numerados de \(1\) a \(n\), y \(m\) enlaces dirigidos: el enlace \(u\) \(v\) \(w\) lleva una señal de \(u\) a \(v\) en \(w\) unidades de tiempo. Se envía una señal desde el nodo \(k\). ¿Cuánto tarda en llegar a todos los nodos? Si algún nodo no la recibe nunca, la respuesta es \(-1\).

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\), \(m\) \((1 \le m \le 2 \cdot 10^5)\) y \(k\) \((1 \le k \le n)\). Cada una de las siguientes \(m\) líneas tiene un enlace \(u\) \(v\) \(w\) \((u \ne v, 0 \le w \le 10^4)\). No hay dos enlaces con el mismo \(u\) y \(v\).

Salida

El tiempo en que el último nodo recibe la señal, o \(-1\).

Ejemplo 1

Entrada

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

Salida

2

Ejemplo 2

Entrada

2 1 1
1 2 1

Salida

1

Ejemplo 3

Entrada

2 1 2
1 2 1

Salida

-1