Description

Given a directed graph with N vertices, M edges. Find the longest path (A path can walk through a same edge more than once) containing at most K edges that starts from S and output the vertex the longest path ends at (We define a path's length as the sum of w_i of each edge on the path, and the longest path is the one with maximum length among all other paths. Note that w_i may be negative).

Note that the solution for the full problem may be difficult, so it may be a wise choice to first get the points of testcases 1 and 2.

 

Input

The first line contains four integers N, M, K, and S, which are the number of vertices, number of edges, how many edges a path can contain at most, and the staring vertex, respectively.

The second to (M + 1)^th line, each line consists of three integers u_i, v_i, and w_i, representing an edge starting from vertex u_i , ending at vertex v_i, with length w_i.

Output

A single integer, the vertex where the longest path containing at most K edges that starts from S ends at, if there are multiple choices, output the one with least index.

Note that there is a newline after the output.

The possibilities of sample input:

2 : length 0

2->1 : length -1

2->3 : length 1

2->1->2 : length 2

2->3->1: length -1

2->1->2->1 : length 1

2->1->2->3 : length 3

2->3->1->2 : length 2

2->1->2->1->2 : length 4

2->1->2->3->1 : length 1

2->3->1->2->1 : length 1

2->3->1->2->3 : length 3

2->1->2->1->2->1 : length 3

2->1->2->1->2->3 : length 5

2->1->2->3->1->2 : length 4

2->3->1->2->1->2 : length 4

2->3->1->2->3->1 : length 1

The longest path is 2->1->2->1->2->3, so we output the ending vertex of this path : 3.

Sample Input  Download

Sample Output  Download

Tags

Discuss