{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cimg src\u003d\"http://r.photo.store.qq.com/psb?/d4a7daf2-8744-4615-88e0-f78921b21cf9/zQPwkekKwZYgV27mc7nkywdgSXBsW28sJ4Jwd4Zy5G8!/r/dB4BAAAAAAAA\"\u003e\u003c/br\u003e\n作为情强,宫代拓留当然会对自己的每一次行动进行充分的准备。\u003c/br\u003e\n他正在为前往AH综合医院调查的路线进行规划。\u003c/br\u003e\n他的情报显示,涉谷由N个建筑,M条街道组成。他所在的位置是S,AH综合医院所在的位置是T。\u003c/br\u003e\n每条街道的情报有:1、是否贴有力士贴纸,2、街道的长度,3、引力异常值\u003c/br\u003e\n宫代拓留作为Gigalo-Maniacs,看到实质为“第十一类罗夏墨迹测验”的力士贴纸会感到不适,他最多能忍受经过A个贴有力士贴纸的街道。\u003c/br\u003e\n因为体力的限制,街道的长度之和不能超过B。\u003c/br\u003e\n而这次行动的花费是他所经过的街道的引力异常值的最大值。\u003c/br\u003e\n他想知道最小的花费是多少。\u003c/br\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"第一行N M S T四个整数(1 ≤ N ≤ 100,1 ≤ M ≤ 1e4,1 ≤ S, T ≤ n)\u003c/br\u003e\n第二行A和B两个整数(0 ≤ A ≤ 1e6,0 ≤ B ≤ 1e6)\u003c/br\u003e\n接下来M行,每行ui vi si li wi五个数。\u003c/br\u003e\n表示第i条街道,从ui到vi(单向),si为1表示贴有力士贴纸,街道长度为li,引力异常值为wi\u003c/br\u003e\n"}},{"title":"Output","value":{"format":"HTML","content":"如果不能在A和B的限制下到达T,直接输出“-1”\u003c/br\u003e\n否则,第一行输出最小花费\u003c/br\u003e\n第二行输出所选路径中包含的街道的条数\u003c/br\u003e\n第三行按经过的顺序输出所选路径中街道的编号,空格分隔\u003c/br\u003e\n"}},{"title":"Example","value":{"format":"HTML","content":"sample input1\u003c/br\u003e\n2 2 1 2\u003c/br\u003e\n1 100\u003c/br\u003e \n1 2 1 100 77\u003c/br\u003e\n1 2 1 100 66\u003c/br\u003e\n\u003c/br\u003e\nsample output1\u003c/br\u003e\n66\u003c/br\u003e\n1\u003c/br\u003e\n2\u003c/br\u003e\n\u003c/br\u003e\nsample input2\u003c/br\u003e\n2 2 1 2\u003c/br\u003e\n0 100\u003c/br\u003e\n1 2 0 101 77\u003c/br\u003e\n1 2 1 100 66\u003c/br\u003e\n\u003c/br\u003e\nsample output2\u003c/br\u003e\n-1\u003c/br\u003e"}}]}