L. Walking to School
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Michael needs to walk to school every day from downtown. There're $$$n$$$ crossings and $$$m$$$ paths connecting these crossings. Michael starts by crossing $$$1$$$ he needs to reach crossing $$$T$$$. Now, because of the fabulous New England weather, each path $$$i$$$ is either covered in snow with depth $$$x_i$$$ or cleared of snow by the hard-working oppressed lower class. Walking in snow is tiring, so walking along each snowy path increases Michael's dreariness $$$d$$$ by $$$1$$$. Further, walking on snow costs Michael energy. The energy of crossing the path $$$i$$$ is $$$d \times x_i$$$. Find the minimum energy Michael needs to get to school.

Input

The first line contains 3 integers $$$n,m,T$$$ $$$(1\le n\le 1000,1\le m\le \min(1000,\frac13 n^2), 1\le T\le n)$$$. The following $$$m$$$ lines each contains 3 integers $$$a_i,b_i,x_i$$$ $$$(1\le a_i,b_i\le n,0\le x_i\le 100)$$$.

Output

Print the minimum energy Michael needs to get to school. Output -1 if he cannot.

Examples
Input
4 4 4
1 2 43
2 4 74
1 3 78
3 4 98
Output
74
Input
5 1 1
3 4 14
Output
0