//2024.4.9
//https://www.acwing.com/problem/content/855/
//853.有边数限制的最短路
/*
思路:核心代码 ————> d[b] = min(d[b], md[a] + c)
只是我们需要处理一下串联的情况,解决代码如右 ————> memcpy(md, d , sizeof d)
*/
#pragma GCC target ("avx")
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
typedef pair<int, int> PII;
const int N = 510, M = 10010;
int n,m,k;
int d[N], md[N];
struct Node{
int a,b,c;
}node[M];
int bellman_ford(){
memset(d, INF, sizeof d);
d[1]=0;
for(int i=0;i<k;i++){//执行k次
memcpy(md, d , sizeof d);
for(int j=0;j<m;j++){
int a = node[j].a, b = node[j].b, c = node[j].c;
d[b] = min(d[b], md[a] + c);
}
}
return d[n];
}
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>m>>k;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
node[i] = {a,b,c};
}
int t = bellman_ford();
if(t > INF/2) cout<<"impossible"<<endl;
else cout<<t<<endl;
return 0;
}