蓝桥王国2 ### 题目描述 小明是蓝桥王国的王子，今天是他登基之日。 在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。 题目的内容如下： 蓝桥王国一共有 $N$ 个建筑和 $M$ 条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为 $1\sim N$ 。（其中皇宫的编号为 $1$）从皇宫到每个建筑的最短路径是多少？ 经过你的帮助，小明轻松的回答了该问题，但是国王的考验并不仅仅这么简单。很快国王又提出了一个问题，他要小明回答从建筑 $S$ 到建筑 $T$ 的第 $K$ 短路的长度为多少？ 小明此时已经失去了思考能力，作为他的好朋友，请你再次帮帮他。 ### 输入描述 输入第一行包含三个正整数 $N,M$。 第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\rightarrow v$ 之间存在一条距离为 $w$ 的路。 第 $M+2$ 行包含三个正整数 $S,T,K$。 $1\leq S,T\leq N \leq 10^3$，$1 \leq m \leq 10^5$，$1 \leq u_i, v_i\leq N$，$0 \leq w_i \leq 10 ^ 3$，保证 $S\neq T$。 ### 输出描述 输出占一行，包含一个整数，表示 $S\rightarrow T$ 的第 $K$ 短路的长度，如果第 $K$ 短路不存在，则输出 $−1$。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 4 1 3 9 1 2 3 1 2 1 2 3 2 1 3 1 ``` >输出 ```txt 3 ``` #### 示例2 >输入 ```txt 3 4 1 3 9 1 2 3 1 2 1 2 3 2 1 3 10 ``` >输出 ```txt -1 ```