code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
template<typename Type>
struct Graph
{
	Graph(){Clean();}
	const static int Maxm=4e4+1e3;
	const static int Maxn=4e3+1e2;
	const static int Maxk=4e3+1e2;
	int len,cnt;
	int From[Maxm],To[Maxm],Next[Maxm];Type Cost[Maxm];
	int Last[Maxn],Dist[Maxn][Maxk];
	inline void Clean(){len=0;memset(Last,-1,sizeof(Last));}
	inline void Insert(int from,int to,Type cost)
	{
		From[len]=from;To[len]=to;Cost[len]=cost;
		Next[len]=Last[from];Last[from]=len++;
	}
};
const int Maxn=4e3+1e2;
bool Visit[Maxn];
queue<int>Q;
template<typename Type>
inline void Bellman_Ford(Graph<Type>* G,int strat,int k)
{
	while(!Q.empty())Q.pop();Q.push(strat);
	memset(G->Dist,0x3f,sizeof(G->Dist));G->Dist[strat][0]=0;
	memset(Visit,false,sizeof(Visit));Visit[strat]=true;
	while(!Q.empty())
	{
		int from=Q.front();Q.pop();Visit[from]=false;
		for(int k=G->Last[from];k!=-1;k=G->Next[k])
		{
			int to=G->To[k];
			if(G->Dist[to][0]>max(G->Dist[from][0],G->Cost[k]))
			{
				G->Dist[to][0]=max(G->Dist[from][0],G->Cost[k]);
				if(Visit[to]==false)
				{
					Q.push(to);
					Visit[to]=true;
				}
			}
			for(int j=1;j<=k;j++)
			{
				if(G->Dist[to][j]>min(G->Dist[from][j-1],max(G->Dist[from][j],G->Cost[k])))
				{
					G->Dist[to][j]=min(G->Dist[from][j-1],max(G->Dist[from][j],G->Cost[k]));
					if(Visit[to]==false)
					{
						Q.push(to);
						Visit[to]=true;
					}
				}
			}
		}
	}
}
Graph<int>G;
int n,p,k;
int main()
{
	scanf("%d%d%d",&n,&p,&k);
	for(int i=1;i<=p;i++)
	{
		int from,to,cost;
		scanf("%d%d%d",&from,&to,&cost);
		G.Insert(from,to,cost);
		G.Insert(to,from,cost);
	}
	Bellman_Ford(&G,1,k);
	int ans=1e9;
	for(int i=0;i<=k;i++)
		ans=min(ans,G.Dist[n][i]);
	if(ans==1e9)ans=-1;
	printf("%d\n",ans);
	return 0;
}