ll@(N,C,V),@(S--)[V],@(T--)[V],@Y[V],@M[V];
vector<vector<array<ll,3>>>G(N);
rep(i,V)G[S[i]].push_back({T[i], Y[i], M[i]});
Heap<array<ll,3>>hq;hq.walloc(2<<17);
ll dp[N][C+1];rep(i,N)rep(j,C+1)dp[i][j]=1d18;
dp[0][C]=0;
hq.push({0,0,C});
while(hq.size) {
    auto[e,v,c]=hq.pop();
    if(dp[v][c]!=e)continue;
    for(auto[u,y,m]:G[v]){
        ll nc=c-y;
        if(nc>=0&&dp[u][nc]>dp[v][c]+m){
            dp[u][nc]=dp[v][c]+m;
            hq.push({dp[u][nc],u,nc});
        }
    }
}
ll ans = 1d18;
rep(i,C+1)ans<?=dp[N-1][i];
wt(ans==1d18?-1:ans);