{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\"好男人从不让女孩等待或违约！\" 鸳鸯父亲说。他轻轻地摸着小鸭子的头，给他们讲了一个故事。\r\u003cbr\u003e\r\u003cbr\u003e\"雷马古茨王子住在他的王国 UDF - 自由联盟三角洲。有一天，他们的邻国派来了乌玉公主进行外交任务。\"\r\u003cbr\u003e\r\u003cbr\u003e\"不久前，公主给雷马古茨写了一封信，告诉他如果且仅如果王子走K个最短路径去见她，她会来大厅与UDF进行商谈。（实际上，乌玉并不想来）\"\r\u003cbr\u003e\r\u003cbr\u003e对于贸易发展和如此可爱的女孩，雷马古茨王子真的迷恋上了。他需要你 - 首相的帮助！\r\u003cbr\u003e\r\u003cbr\u003e细节：UDF的首都由N个车站组成。大厅编号为S，而编号为T的车站表示王子当前所在地。M个泥泞的有向边连接了一些车站。雷马古茨迎接公主的路径可能包括同一车站两次或多次，甚至是编号为S或T的车站。相同长度的不同路径将被视为不同的路径。\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含两个整数N和M（1 \u003c\u003d N \u003c\u003d 1000，0 \u003c\u003d M \u003c\u003d 100000）。车站从1到N编号。接下来的M行中，每行包含三个整数A，B和T（1 \u003c\u003d A，B \u003c\u003d N，1 \u003c\u003d T \u003c\u003d 100）。它表示从A号车站到B号车站有一条时间为T的有向边。\r\u003cbr\u003e\r\u003cbr\u003e最后一行由三个整数S，T和K（1 \u003c\u003d S，T \u003c\u003d N，1 \u003c\u003d K \u003c\u003d 1000）组成。"}},{"title":"输出","value":{"format":"HTML","content":"一行，包含一个整数：使用第K个最短路径迎接乌玉公主所需的长度（时间）。如果第K个最短路径不存在，则应输出“-1”（不带引号）。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2\r\n1 2 5\r\n2 1 4\r\n1 2 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}