By Microsoft Serbia
You are playing a simple game. You are given an undirected connected graph which does not have cycles. There is also one coin with is in the beginning located at vertex X. One step consists of moving the coin from the vertex at which it is currently located to any adjacent vertex (two vertexes are adjacent if there is an edge connecting them). Every edge has an associated number of points you gain if you move the coin from one of its vertexes to another. Your task is to calculate the maximal number of points you can gain in K steps. You can move the coin along some edges more than once.
The first line contains number N, which is the number of vertexes of the tree (number of vertexes 2 ≤ N ≤ 100000). The following N - 1 lines contain information for N - 1 edges of the tree. Each of the following N - 1 lines has three numbers ( i-th of these lines describes i-th edge) – the first two numbers are vertexes connected by the edge and the third number is the number of points that you gain if you move the coin along that edge. The number of points associated with an edge is less or equal to 1000. The vertexes are labeled with numbers from 1 to N.
The next line contains the number K, 1 ≤ K ≤ 100000.
The last line contains the vertex X, vertex at which the coin is located in the beginning.
You should output one number which is the maximal number of points you can gain in K steps with the coin located in the beginning at vertex X.
|Input Sample||Output Sample|
1 2 3
4 3 5
4 1 2
3 6 6
5 1 9