//Accepted 508 KB 79 ms
//spfa+二分
//二分需要的花费cost，把图中大于cost的边设为1,小于cost的边设为0,然后spfa求
//最短路，如果小于K则可行，继续二分
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
/**
* This is a documentation comment block
* 如果有一天你坚持不下去了，就想想你为什么走到这儿！
* @authr songt
*/
;
;
;
struct node
{
int u,v,c;
node()
{
}
node(int u,int v,int c):u(u),v(v),c(c)
{
}
}p[imax_e];
int e;
bool vis[imax_n];
int head[imax_n];
int next[imax_e];
int dis[imax_n];
int n,m,K;
void init()
{
memset(head,-,sizeof(head));
memset(next,-,sizeof(next));
e=;
}
void addEdge(int u,int v,int c)
{
p[e]=node(u,v,c);
next[e]=head[u];
head[u]=e++;
}
bool relax(int u,int v,int c)
{
if (dis[v]>dis[u]+c)
{
dis[v]=dis[u]+c;
return true;
}
return false;
}
queue<int > q;
bool spfa(int src,int len)
{
while (!q.empty()) q.pop();
memset(vis,false,sizeof(vis));
;i<=n;i++)
{
dis[i]=inf;
}
dis[src]=;
q.push(src);
vis[src]=true;
while (!q.empty())
{
int pre=q.front();
q.pop();
vis[pre]=false;
;i=next[i])
{
:;
if (relax(pre,p[i].v,c) && !vis[p[i].v])
{
vis[p[i].v]=true;
q.push(p[i].v);
}
}
}
if (dis[n]<=K) return true;
else return false;
}
int main()
{
while (scanf("%d%d%d",&n,&m,&K)!=EOF)
{
init();
int u,v,c;
,right=,mid;
;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&c);
right=right>c?right:c;
addEdge(u,v,c);
addEdge(v,u,c);
}
,right)==)
{
printf("-1\n");
continue ;
}
while (left<=right)
{
mid=(left+right)/;
//printf("left=%d right=%d mid=%d\n",left,right,mid);
,mid))
{
right=mid-;
}
else
{
left=mid+;
}
}
printf();
}
}
