**Problem Description**

**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绍兴市联赛