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

Fito saco un pasaje para Egipto para realizar un documental sobre los nómadas en el Sahara.  Transitar por el desierto es muy peligroso por las altas temperaturas que tiene que soportar el cuerpo humano. Por lo que quiere planificar el viaje con antelación.  Por lo que él siempre tiene que evitar pasar por las rutas que poseen la mayor temperatura, aunque dependiendo del destino puede ser la única vía por lo que no le queda más remedio que cruzarla.  Por lo que a la hora de tomar un camino  siempre tiene que escoger aquella cuya mayor temperatura sea mínima. Si hay varias que cumplen con el mismo criterio entonces se tomara la más corta.

En el desierto hay diferentes oasis, por lo que el viaje se realiza transitando de un oasis al otro hasta llegar al destino.  Se conocen las distancias entre los oasis y las temperaturas de las vías entre ellas.  Por lo que depende de nosotros que Fito pueda realizar un buen documental y que no se enferme por el calor.

Input

La primera línea contiene dos enteros, $N$ y $E$ $(1 \leq N \leq 100; 1 \leq E \leq 10000)$, donde $N$ representa la cantidad de oasis y $E$ representa la cantidad de caminos que hay entre los oasis.  La próxima línea contiene dos números distintos $S$ y $T$ $(1 \leq S,T \leq N)$ que representa el punto de salida y el punto de llegada. Luego son $E$ líneas, cada línea cuatro números separados por un espacio, los dos primeros son números enteros $X$ y $Y$ que representa el oasis de origen y el oasis de llegada de la vía y los otros dos números son reales $R$ y $D$ $(1 \leq X, Y \leq N; 20 \leq R \leq 50; 0 \lt D \leq 40)$ que representan la máxima temperatura en grados Celsius y la distancia en km. Estos números reales tienen un digito después de la coma. Puede haber más de un camino entre cualquier par de oasis.

Output

Se imprimen dos líneas, la primera es el camino para transitar desde el oasis de partida la de llegada. Y la segunda línea es la distancia del camino y la máxima temperatura.

Sample test(s)