## Simplified Travelling Salesman Problem

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 9   Accepted Submission(s): 4
Problem Description

There are n cities in Kingdom xxx and m undirected roads connecting the cities. A travelling salesman starts from city s and wants to travel around the kingdom. Now you need to tell him the shortest path.

Input

Multiple cases (<= 10).
For each test case, the first line consists of three integers n, m, s (1 <= n <= 16, m <= 10000, 1 <= s <= n). Then m lines follow, each line consists of three integers u, v, w (1 <= u, v <= n; 0 <= w <= 100), representing two endpoints and length of a road.

Output

For each test data, output one line, representing answer. If the travelling salesman cannot travel around the kingdom, output -1.

Sample Input
```5 5 1
1 2 2
1 3 3
1 4 4
1 5 5
4 5 6
```
Sample Output
```20
```
Source

2017绍兴市联赛
{"ft_lang_label":"__label__en","ft_lang_prob":0.88439995,"math_prob":0.9800721,"size":728,"snap":"2020-45-2020-50","text_gpt3_token_len":212,"char_repetition_ratio":0.10082873,"word_repetition_ratio":0.014285714,"special_character_ratio":0.32005495,"punctuation_ratio":0.14102565,"nsfw_num_words":1,"has_unicode_error":false,"math_prob_llama3":0.97958016,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-11-25T10:44:34Z\",\"WARC-Record-ID\":\"<urn:uuid:e27488f4-ff18-47d8-8914-87c931f0311d>\",\"Content-Length\":\"12050\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5221c301-696e-4e7a-9be6-d97a850241d3>\",\"WARC-Concurrent-To\":\"<urn:uuid:e19131a7-cfa6-4005-b117-38ca2d1998bc>\",\"WARC-IP-Address\":\"61.174.215.231\",\"WARC-Target-URI\":\"http://acm.usx.edu.cn/AspNet/Question.aspx?qid=1600\",\"WARC-Payload-Digest\":\"sha1:GXF3OPVBW2WQTOOK3X3J6HPUXQQOSCZ7\",\"WARC-Block-Digest\":\"sha1:4ZHV6JJGWLRWMBSR4BET7DEEQXEGTVH3\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141182776.11_warc_CC-MAIN-20201125100409-20201125130409-00319.warc.gz\"}"}