#include<bits/stdc++.h> using namespace std; const int N=114514; //李思贤日CCF int dist[N],backup[N]; int k,n,m; //一次一次一次换了多少个CCF，有用吗，换汤不换药啊！ struct edge{ int a; int b; int w; }edge[N]; //三锭多了，做个卵啊做，应擦线啊！ int bellman_ford(){ memset(dist,0x3f,sizeof(dist)); dist[1]=0; for(int i=1;i<=k;i++){ memcpy(backup,dist,sizeof dist); for(int j=1;j<=m;j++){ //你是故意找BUG是吧？！ int a=edge[j].a,b=edge[j].b,w=edge[j].w; //Never gonna give you up //Never gonna let you down //Never gonna round a round and hurt you dist[b]=min(dist[b],backup[a]+w); } } return dist[n]; //送给你小心心，送你花一朵 //你在我生命中，太多的感动 //你是我的天使，一路指引我 //无论岁月变换，爱你唱成歌 //听我说谢谢你，因为有你，温暖了四季 //谢谢你，因为有你，世界更美丽 //听我说谢谢你，因为有你，爱藏在心底 //谢谢你，因为有你，世界更美丽 } int main(){ cin>>n>>m>>k; //我年纪轻轻就打了3200次CCF for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; edge[i].a=a,edge[i].b=b,edge[i].w=c; //小朋友们，CCF里的你再强大，也是假的，应该被丢进垃圾桶 } int t=bellman_ford(); if(t>=0x3f3f3f3f/2) cout<<"imposible"; else cout<<t<<endl; return 0; //啊哈哈哈，我滴代码完成啦！ }