Hay \(n\) ciudades, numeradas de \(0\) a \(n - 1\), unidas por \(m\) caminos bidireccionales con pesos. Para cada ciudad, cuenta cuántas otras ciudades están a distancia (de camino más corto) a lo más \(D\). Encuentra la ciudad con el menor conteo; si hay empate, la de mayor número.

Entrada

La primera línea tiene \(n\) \((2 \le n \le 100)\), \(m\) \((1 \le m \le n(n-1)/2)\) y \(D\) \((1 \le D \le 10^4)\). Cada una de las siguientes \(m\) líneas tiene un camino \(a\) \(b\) \(w\) \((a \ne b, 1 \le w \le 10^4)\). No hay caminos repetidos.

Salida

El número de la ciudad.

Ejemplo 1

Entrada

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

Salida

3

Ejemplo 2

Entrada

5 6 2
0 1 2
0 4 8
1 2 3
1 4 2
2 3 1
3 4 1

Salida

0