{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\"好男人永远不会让女孩等待或爽约!\" 鸳鸯父亲说。他轻轻地摸着他小鸭子的头,给它们讲故事。\u003cbr\u003e\u003cbr\u003e\"雷马古茨王子生活在他的王国 UDF - 自由联合三角洲。一天,他们邻国派来了公主乌宇威进行外交任务。\"\u003cbr\u003e\u003cbr\u003e\"不久前,公主给雷马古茨写了一封信,告诉他她只有在王子通过第 K 短的路径去见她时,才会前来大厅与 UDF 进行商谈。(事实上,乌宇威根本不想来)\"\u003cbr\u003e\u003cbr\u003e对于贸易发展和如此可爱的女孩感兴趣,雷马古茨王子真的陶醉了。他需要你 - 首相的帮助!\u003cbr\u003e\u003cbr\u003e细节:UDF 的首都由 N 个车站组成。大厅编号为 S,而编号为 T 的车站表示王子当前的位置。M 条泥泞的有向边连接了一些车站。雷马古茨迎接公主的路径可能包括同一车站两次或两次以上,即使是编号为 S 或 T 的车站。相同长度的不同路径将被视为不同。\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 的有向边。\u003cbr\u003e\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"}}]}