在数码世界中有一个叫做“Radiation Zone”的区域，里面荒无人烟，仿佛遗迹一般。在这个区域中有N个城市（假设编号为从0到N-1），每个城市中都有一定数量的辐能。有M条已知长度的道路连接它们，每条道路都可以双向来往。

近期这个区域似有黑暗气息蛰伏，国王Shoutmon派出调查队前来调查这个区域中的城市。调查队的飞船降落在S号城市。由于飞船降落时气流不稳定，因此产生了辐能波，导致以S号城市为中心的L层以内（假设S号城市为最内层，记为第0层）的城市的辐能都会上升（只上升一次），上升的数值为 “城市的当前辐能乘以百分比p”的向上取整。其中百分比p在S号城市时为100%，且每向外扩散一层，百分比降低100%/L（例如，如果L为5，那么第0层（即S号城市）为100%，第1层为80%，第2层为60%，第3层为40%，第4层为20%，其中百分比均为浮点数）。所谓第X层是指，连接某城市与S号城市的最少数量的道路数，例如下图是一个例子，图中的数字为其层号。

之后调查队需要前往T号城市调查。为了顺便清除城市中的辐能，他们准备了一个容量为K的辐能吸收器。辐能吸收器可以自动吸收城市中的辐能，且满容量时会自动将容器内的所有辐能都燃烧完毕，以继续吸收辐能。假设调查队总是把城市（含S号和T号城市）中的辐能吸收完毕。

为了节省体力，调查队希望选择一条长度最短的路径前往T号城市；如果这样的路径有多条，那么从中选择到达T号城市时辐能吸收器内当前辐能最大的路径；如果这样的路径仍然有多条，那么从中选择路径后半段的城市的辐能之和最小的路径（所谓后半段是指，如果路径上有m个城市，那么后m/2个城市（含T号城市）是后半段的城市。例如，如果路径上有7个城市，那么路径的后3个城市（除法为向下取整）为后半段的城市）。数据保证这样的路径一定唯一。

每个输入文件中一组数据。

第一行六个整数N、M、L、K、S、T（2<=N<=500, M<=N*(N-1)/2, 1<=L<=500, 2<=K<=100, S != T），分别代表城市个数、道路条数、辐能上升的层数、辐能吸收器的容量、起点城市编号、终点城市编号。

接下来一行有N个正整数，分别给出N个城市的初始辐能（均为不超过100的正整数）。

接下来M行，每行三个数字u、v、w，代表一条道路，其中u和v为道路的两个端点城市编号，w为道路的长度（w为不超过1000的正整数）。数据保证u不等于v，且相同的无序对(u,v)只出现一次。

如果从S号城市不能到达T号城市，那么只输出-1。

如果从S号城市能到达T号城市，那么输出两行：

第一行输出四个整数， 即S号城市到T号城市的最短距离的路径条数（数据保证不超过100000条）、S号城市到T号城市的最短距离、通过最终选择的路径到达T号城市时辐能吸收器内的当前辐能、最终选择的路径的后半段城市的辐能之和。

第二行输出最终选择的路径，路径上的城市之间用->隔开。