Constrained Shortest Path in Graph

Given an undirected graph with (n) vertices and (m) edges, each edge has two weights: (t_i) and (h_i). You are also given three integers (s), (t) and (k). Your task is to find a path from vertex (s) to vertex (t) such that the sum of (h_i) over all edges on the path is strictly less than (k) (i.e. (\sum h_i < k)) and the sum of (t_i) is minimized. Output the minimum sum of (t_i) for such a valid path, or (-1) if no path exists.

inputFormat

The first line contains five space-separated integers: \(n\), \(m\), \(s\), \(t\), and \(k\).

Each of the following \(m\) lines describes an edge with four space-separated integers \(u\), \(v\), \(t_i\) and \(h_i\), representing an undirected edge between vertices \(u\) and \(v\) with weight \(t_i\) and cost \(h_i\).

\(1 \leq u,v \leq n\).

outputFormat

Output a single integer: the minimum total \(t_i\) along a valid path from \(s\) to \(t\) satisfying \(\sum h_i < k\). If no valid path exists, output \(-1\).

sample

3 3 1 3 5
1 2 2 3
2 3 3 1
1 3 10 6

5