Hay un grafo conexo no dirigido de \(N\) vértices y \(M\) aristas con largos positivos (a lo más una arista entre cada par). Una persona sale de \(P\) y siempre viaja por un camino más corto; se cansa justo a la mitad de la distancia que recorre.

Se busca un destino \(Q\) tal que todo camino más corto de \(P\) a \(Q\) pase por \(G\) y la persona se canse exactamente en \(G\), es decir, \(d(P, Q) = 2 \cdot d(P, G)\) y \(G\) está en todos los caminos más cortos de \(P\) a \(Q\). Encuentra todos los \(Q\) que cumplen esto.

Entrada

La primera línea tiene dos enteros \(N\) \((2 \le N \le 10^5)\) y \(M\) \((1 \le M \le 10^5)\).

La segunda línea tiene dos enteros \(P\) y \(G\) \((1 \le P, G \le N,\ P \ne G)\).

Cada una de las siguientes \(M\) líneas tiene tres enteros \(U\), \(V\) y \(D\) \((1 \le U, V \le N,\ U \ne V,\ 1 \le D \le 10^9)\): una arista de largo \(D\).

Salida

Una línea con los vértices que sirven, en orden creciente, o el carácter * si no hay ninguno.

Ejemplo 1

Entrada

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

Salida

2 4

Ejemplo 2

Entrada

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

Salida

4

Ejemplo 3

Entrada

3 2
1 2
1 2 100000
2 3 99999

Salida

*

Ejemplo 4

Entrada

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

Salida

*

Regional Latinoamericana 2023 del ICPC, problema M («Meeting Point»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.