Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 1010

#define MAXM 10010

struct edge

{

	int to,nxt,v,l;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c,0};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c,0};lin[b] = edgenum;

	return;

}

int d[MAXN];

bool v[MAXN];

bool check(int l)

{

	for(int i = 1;i <= edgenum;++i)

		if(e[i].v > l)e[i].l = 1;

	memset(d,0x3f,sizeof(d));d[1] = 0;

	queue<int> q;q.push(1);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].l)

			{

				d[e[i].to] = d[k] + e[i].l;

				if(!v[e[i].to])

				{

					q.push(e[i].to);

					v[e[i].to] = true;

				}

			}

		}

	}

	for(int i = 1;i <= edgenum;++i)e[i].l = 0;

	return (d[n] <= k);

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	int l = 0,r = 1000001,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(check(mid))r = mid;

		else l = mid + 1;

	}

	if(l != 1000001)cout << l << endl;

	else puts("-1");

	return 0;

}