//时间复杂度为 O(nm)

,,,

const int N = 1e4 + 10;
int n, m, k;
int d[N], last[N];

struct Edge{
int a, b, c;
}edges[N];

void bellman_ford()
{
memset(d, 0x3f, sizeof d); //初始化所有点，不可以到达1号点
d[1] = 0; //1号点可以到达1号点，更新入口；

for(int i = 1; i <= k; i++)  //经过不超过k条边，到达源点的最短距离； 
{                            //时间复杂度为 O(nm); 因为n个点最多需要n-1条边连通；
    memcpy(last, d, sizeof d);  //每一次用上次更新的数据，

    for(int i = 0; i < m; i++)
    {
        auto e = edges[i];
        d[e.b] = min(d[e.b], last[e.a] + e.c);  // 例如两条边 a-c，c-b；循环会先更新d[c],
                                                // 到更新d[b]的时候，会用刚刚更新的d[c];它的实际意义就是，b经过两条边到a; 
    }

}

}

int main(){

cin>>n>>m>>k;
int a, b, c;
for(int i = 0; i < m; i++)
{
    scanf("%d%d%d", &a, &b, &c);
    edges[i] = {a, b, c};
}

bellman_ford();

if(d[n] > 0x3f3f3f3f/2) cout<<"impossible";  //在负权图中，表示“不可达”不再是0x3f3f3f3f, 而是根据题意
                                             //找一个“较大值”来衡量。
else cout<<d[n];

return 0;

}
,,,