题意：
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。
该市周围分布着N(1<=N<=1000)根据1……n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(1<=p<=10000)对电话杆可以拉电话线。
其他的由于地震使得无法连接。
第i对电线杆的两个端点分别是ai,bi，它们的距离为li(1<=li<=1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电话网络，
整个市的电话线全都连到了编号N的电话线杆上。也就是说，笨笨的任务仅仅是找一条将1号和N号电线杆连起来的路径，其余的电话杆并不一定要连入电话网络。
电信公司决定支援灾区免费为此市连接k对由笨笨指定的电话线杆，对于此外的那些电话线，需要为它们付费，总费用决定于其中最长的电话线的长度
(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过k对，那么支出为0.
请你计算一下，将电话线引导震中市最少需要在电话线上花多少钱？
析：二分最长的电话线长度，然后每次跑一次最短路dijkstra，每次都是把权值大于二分的长度边设为1，其他的设置为0，每次判断最短路是不是小于k即可。
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#define debug() puts("++++");
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int mod = 1e6;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
vector<int> G[maxn], w[maxn];
int d[maxn];
int k;
int dijkstra(int m){
priority_queue<P, vector<P>, greater<P> > pq;
fill(d, d + n + 1, INF);
d[1] = 0;
pq.push(P(0, 1));
while(!pq.empty()){
P pp = pq.top(); pq.pop();
int u = pp.second;
if(u == n) return pp.first <= k;
if(d[u] < pp.first) continue;
for(int i = 0; i < G[u].size(); ++i){
int v = G[u][i];
if(d[v] > d[u] + (w[u][i] > m)){
d[v] = d[u] + (w[u][i] > m);
pq.push(P(d[v], v));
}
}
}
return -1;
}
int solve(){
int l = 0, r = 1000000;
while(l < r){
int m = l+r >> 1;
int t = dijkstra(m);
if(t < 0) return -1;
if(t) r = m;
else l = m+1;
}
return dijkstra(l) ? l : l-1;
}
int main(){
while(scanf("%d %d %d", &n, &m, &k) == 3){
for(int i = 1; i <= n; ++i) G[i].clear(), w[i].clear();
int u, v, val;
for(int i = 0; i < m; ++i){
scanf("%d %d %d", &u, &v, &val);
G[u].push_back(v);
G[v].push_back(u);
w[u].push_back(val);
w[v].push_back(val);
}
printf("%d
", solve());
}
return 0;
}