o58_oct_c2_routesontrees

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int K = 5 + 10;
const int inf = 1e9;
using pi = pair <int, int>;
using pii = pair <int, pi>;
vector <pi> g[N];
int dis[N][K];
bool vs[100010][15];

int main(){

    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1;i<=m;i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        g[u].push_back({v, w});
    }

    for(int i=0;i<=n;i++){
        for(int j=0;j<=k;j++){
            dis[i][j] = inf;
            vs[i][j] = false;
        }
    }


    priority_queue <pii, vector <pii>, greater <pii>> pq;
    dis[1][0] = 0;
    pq.push({ dis[1][0] , { 1 , 0 } });

    while(!pq.empty()){
        int d = pq.top().first;
        int u = pq.top().second.first;
        int x = pq.top().second.second;
        pq.pop();
        if(vs[u][x]) continue;
        vs[u][x] = true;
        if(u == n){
            printf("%d", d);
            return 0;
        }
        for(auto vw: g[u]){
            int v = vw.first;
            int w = vw.second;
            if(w > 0){
                if(!vs[v][x] and d + w < dis[v][x]){
                    dis[v][x] = d + w;
                    pq.push({ dis[v][x] , {v, x} });
                }
            }
            else{
                if(w < -100 and x + 1 <= k and !vs[v][x + 1] and d < dis[v][x + 1]){
                    dis[v][x + 1] = d;
                    pq.push({ dis[v][x + 1], {v, x + 1} });
                }
                else if(w >= -100 and !vs[v][x] and d < dis[v][x]){
                    dis[v][x] = d;
                    pq.push({ dis[v][x], {v, x} });
                }
            }
        }
    }

    printf("-1");

    return 0;
}