输入样例：

输出样例：

#include <iostream>

#include <vector>

#include <memory.h>

using namespace std;

const int N = ;

vector<vector<pair<int, int>>> v;

int dist[N];

int back[N];

int n, m, k;

/*

3 3 1

1 2 1

2 3 1

1 3 3

*/

void solveInner(int back[])

{

    for (int i = ; i < v.size(); i++) {

        for (int j = ; j < v[i].size(); j++) {

            int a = i; int b = v[i][j].first; int w = v[i][j].second;

            if (dist[b] > back[a] + w) {

                dist[b] = back[a] + w;

            }

        }

    }

}

int solve()

{

    memset(dist, 0x3f, sizeof(dist));

    dist[] = ;

    //进行n轮

    for (int i = ; i < k; i++) {

        memcpy(back, dist, sizeof dist);

        solveInner(back);

    }

    if (dist[n] > 0x3f3f3f3f / ) return -;

    return dist[n];

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    //cin >> n >> m >> k;

    v.resize(n + );

    for (int i = ; i < m; i++) {

        int a, b, c;

        //cin >> a >> b >> c;

        scanf("%d%d%d",&a,&b,&c);

        v[a].push_back({ b,c });

    }

    int ret = solve();

    if (ret == -) printf("impossible");

    else printf("%d\n",ret); 

    return ;

}