放假了，nsoi的同学准备回家，学校和家之间有许多的城镇（按1到N编号，学校也看成城镇），城镇与城填之间有道路连通。小S的家就位于某个城镇。现在小S想尽快回家，所以他会走一条最短路回家。不过小S还有一双神奇的跑鞋，（它可以让小S从一个城镇到另一个不花时间（可以把距离看成0），当然跑鞋的能量是有限的，他最多可以用3次）。现在要你解决的是小s回家所走过的最短距离。
输入：
第一行四个整数（N，S，H，T）表示点的个数（N<=400),学校的编号，家的编号，以及跑鞋使用的次数。
接下来M行，每行3个数，A,B,C表示A、B城镇的距离为C。
输出：
一个数表示最短距离，不通输出-1.
样例：
输入：
3 1 3 1
1 2 5
1 3 100
2 3 1
输出：
0