H. 烟火拾穗
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
倘若有一天你的仇人变好了，不再杀人，彻底成好人了。

若是这样的话……

你觉得自己还该复仇吗？

——《烟火》

良需要在宵禁之前找到满穗。

鼓楼附近有一些满穗可能藏匿的地点，良知道这些地点的路径，他希望尽快的找遍这些地点。

形式化的：给定一张具有 $$$n$$$ 个点，$$$m$$$ 条边的无向图，起点为 $$$s$$$。

通过一条边所花费的时间为 $$$w_i$$$。

请你计算从 $$$s$$$ 出发走过所有点花费的最小时间是多少。

Input

第一行输入三个整数 $$$n$$$，$$$m$$$，$$$s$$$（$$$1\le n\le 20$$$，$$$n-1\le m \le \frac{n(n-1)}{2}$$$，$$$1\le s\le n$$$），分别表示地点数量，路径数量和良当前所在的起点。

接下来 $$$m$$$ 行，每行输入三个正整数 $$$u_i$$$，$$$v_i$$$，$$$w_i$$$（$$$1\le u_i,v_i\le n$$$，$$$1\le w_i\le 10^9$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 且边权为 $$$w_i$$$ 的边。

保证给定的图为连通图，且不存在重边和自环。

Output

输出一个正整数，表示答案。

Example
Input
4 5 3
1 2 2
2 3 1
3 4 4
1 4 2
2 4 5
Output
5