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.

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.

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