题号：NC22594
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
Island 发生了一场暴乱！现在 Rinne 要和 Setsuna 立马到地上世界去。
众所周知：Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵戒严，虽然主角可以逆天改命强闯，但是为了体验该游戏的平衡性，他们只能穿过不超过 K 次被戒严的城镇。
定义“穿过”：从一个戒严的点出发到达任意一个点，都会使得次数加1
现在他们想从 1 号城镇最快的走到 n 号城镇（即出口），现在他们想让你告诉他们最短需要走多少路。输入描述:
第一行三个整数 n,m,k，分别表示城镇数量，边数量和最多能闯过被戒严的城市的次数。
接下来 n 行，每行一个整数 1 或 0，如果为 1 则表示该城市已被戒严，0 则表示相反。
接下来 m 行，每行三个数 u,v,w，表示在 u 城镇和 v 城镇之间有一条长度为 w 的双向道路。
输出描述:
输出一行一个数字，表示从 1 到 n 的最短路径，如果到达不了的话，请输出 -1。
备注:
保证没有多条道路连接同一对城市，也没有一条道路连向自己。