Maximum Flow with Limited Edge Length

You are given a directed graph with n vertices and m edges. Each edge is described by three integers u, v, and w indicating a directed edge from vertex u to vertex v with capacity w. It is guaranteed that for every edge, the difference between the endpoints satisfies \( v - u \in [0, k] \) (i.e. \( 0 \le v - u \le k \)). Your task is to compute the maximum flow from vertex 1 to vertex n.

Problem Details

The input begins with three integers n, m, and k. Following that are m lines; each line contains three integers u, v, and w representing a directed edge from vertex u to vertex v of capacity w. The constraint \( v - u \in [0, k] \) holds for every edge.

Task

Calculate and output the maximum amount of flow that can be sent from vertex 1 to vertex n.

inputFormat

The first line contains three integers n, m, and k (\(1 \le n \le 10^5\), etc.). Each of the following m lines contains three integers u, v, and w indicating there is a directed edge from vertex u to vertex v with capacity w. It is guaranteed that \( v - u \in [0, k] \) for every edge.

outputFormat

Output a single integer: the maximum flow from vertex 1 to vertex n.

sample

4 5 2
1 2 10
1 3 10
2 3 5
2 4 4
3 4 10

14