#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
const int M = 10010;
struct edge{
    int a, b, w;
}e[M];
int n, m, k;
int dist[N];
int backup[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 = 0; j < m; j++)
        {
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    if(dist[n] > 0x3f3f3f3f/2) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m >> k;

    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int ans = bellman_ford();
    if(ans == -1) puts("impossible");
    else cout<< dist[n] <<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
struct edge{
    int to, cost;
};
bool st[N];
int dist[N];
vector<edge> e[N];
int n, m;
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue <PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    dist[1] = 0;
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = 0; i < e[ver].size(); i++)
        {
            int newnode = e[ver][i].to;
            int len = e[ver][i].cost;
            if(dist[newnode] > len + dist[ver])
            {
                dist[newnode] = len + dist[ver];
                heap.push({dist[newnode], newnode});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a; edge f;
        scanf("%d%d%d",&a,&f.to,&f.cost);
        e[a].push_back(f);
    }
    cout<<dijkstra()<<endl;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int f[N][2];
int happy[N];
int h[N], e[N], ne[N], idx;
bool has_fa[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> happy[i];
    }
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        has_fa[a] = true;
        add(b, a);
    }
    int root;
    for(int i = 1; i <= n; i++)
    {
        if(!has_fa[i])
        {
            root = i;
            break;
        }
    }

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1]));
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=310;
int f[N][N];
int h[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int r, c;
int dp(int x, int y)
{
    int &v = h[x][y];
    if(v != -1) return v;
    v = 1;
    for(int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1&&a <= r&&b >= 1&&b <= c&&f[a][b] < f[x][y])
            v = max(v, dp(a, b) + 1);
    }
    return v;
}

int main()
{
    cin >> r >> c;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            cin >> f[i][j];
    memset(h, -1, sizeof h);
    int res = 0;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            res = max(res, dp(i, j));

    cout << res <<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=21, M=1<<21;
int w[N][N];
int f[M][N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> w[i][j];
    memset(f, 0x3f3f, sizeof f);

    f[1][0]=0;

    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            if(i >> j & 1)
            {
                for(int k = 0; k < n; k++)
                {
                    if(i-(1 << j) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                }
            }
    cout<<f[(1 << n) - 1][n-1]<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=12;
const int M=1<<12;
long long f[N][M];
bool st[M];
int n, m;

int main()
{
    while(cin>>n>>m, n||m)
    {
        memset(f, 0, sizeof f);
        for(int i = 0; i < 1 << n; i++)
        {
            int cnt = 0;
            st[i] = true;
            for(int j = 0; j < n; j++)
            {
                if(i >> j & 1)
                {
                    if(cnt%2==1) 
                    {
                        st[i]=false;
                        cnt=0;
                    }
                }
                else cnt++;
            }
            if(cnt%2==1) st[i] = false;
        }
        f[0][0]=1;

        for(int i = 1; i <= m; i++)
            for(int j = 0; j < 1 << n; j++)
                for(int k = 0; k < 1 << n ; k++)
                {
                    if((j & k) == 0 && st[j | k])
                    {
                        f[i][j] += f[i-1][k];
                    }
                }
        cout<<f[m][0]<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int dgt(int n)
{
    int res=0;
    while(n)
    {
        res++;
        n/=10;
    }
    return res;
}

int get_ans(int n, int i)
{
    int d=dgt(n), res=0;
    for(int j = 1 ; j <= d ; j++)
    {
        int p=pow(10,j-1);
        int l=n/p/10; int r=n%p; int dg=n/p%10;
        if(i)
        {
            res += l*p;
            if(dg==i)
            {
                res += r+1;
            }
            if(dg > i)
            {
                res+=p;
            }
        }
        if(!i)
        {
            if(l!=0)
            {
                res+=p*(l-1);
                if(dg>i) res+=p;
                if(dg==i) res+=r+1;
            }
        }
    }
    return res;
}

int main()
{
    int a, b;
    while(1)
    {
        scanf("%d%d", &a, &b);
        if(a==0&&b==0) break;
        if(a>b) swap(a,b);
        for(int i=0;i<=9;i++)
        {
            printf("%d ", get_ans(b,i)-get_ans(a-1,i));
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e3 + 7, mod = 1e9 + 7;

int f[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=1;
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=n;j++)
    {
        f[i][j]=f[i-1][j]%mod;
        if(j>=i)
        {
            f[i][j]=(f[i-1][j]%mod+f[i][j-i]%mod)%mod;
        }
    }
    printf("%d", f[n][n]);
    return 0;
}

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int x, y;
char s[1010][20];
int f[100][100];
int min_dis(char a[], char b[])
{
    int lena=strlen(a+1);
    int lenb=strlen(b+1);
    memset(f, 0x3f3f3f, sizeof(f));
    for(int i=1; a[i]!='\0'; i++) f[i][0]=i;
    for(int j=1; b[j]!='\0'; j++) f[0][j]=j;
    f[0][0]=0;
    for(int i=1;i<=lena;i++)
    {
        for(int j=1;j<=lenb;j++)
        {
            f[i][j]=min(f[i][j-1]+1, f[i-1][j]+1);
            if(a[i]==b[j]) f[i][j]=min(f[i][j], f[i-1][j-1]);
            else f[i][j]=min(f[i][j], f[i-1][j-1]+1);
        }
    }
    return f[lena][lenb];
}

int main()
{
    cin>>x>>y;
    for(int i=1;i<=x;i++)
    {
        scanf("%s", s[i]+1);
    }
    while(y--)
    {
        char p[20];
        int tag;
        int ans=0;
        scanf("%s%d", p+1, &tag);
        for(int i=1;i<=x;i++)
        {
            if(min_dis(s[i], p)<=tag)
            {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int n, m;
char a[1010], b[1010];
int f[1010][1010];
int main()
{
    scanf("%d%s",&n, a+1);
    scanf("%d%s",&m, b+1);
    memset(f, 0x3f3f3f, sizeof(f));
    for(int i=1; a[i]!='\0'; i++) f[i][0]=i;
    for(int j=1; b[j]!='\0'; j++) f[0][j]=j;
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(f[i][j-1]+1, f[i-1][j]+1);
            if(a[i]==b[j]) f[i][j]=min(f[i][j], f[i-1][j-1]);
            else f[i][j]=min(f[i][j], f[i-1][j-1]+1);
        }
    }
    printf("%d", f[n][m]);
    return 0;
}