"""

題目：設有n個城市組成的交通圖，一個售貨員從住地城市q出發，到其它城市各一次去推銷貨物，最后回到住地城市。

要求：假定兩個城市a，b 從a到b的路程花費w_ab是已知的，問應該怎樣選擇一條花費最少的路線？

輸入格式：

第一行n m q，n和m兩個整數分別表示城市數n以及城市之間的單向路數量m，q表示住地城市（出發城市）

之后m行 a b w分別表示從城市a到城市b的單向路程的花費w_ab。

輸出格式：

第一行輸出最小花費是D,D表示計算得到的最小花費。

第二行輸出最小花費共有N種方案,分別是:,N表示最小花費方案的種類，

接下來N行輸出每種方案的前往順序，以字典序排序輸出，中間以空格分隔。

輸入樣例：

3 6 A

A B 12

A C 4

B C 5

B A 8

C B 7

C A 2

輸出樣例：

最小花費是19

最小花費共有2種方案,分別是:

A B C

A C B

"""

from itertools import permutations
import sysdef tsp(n, m, q, edges):# 將城市名稱轉換為索引city_to_index = {chr(ord('A') + i): i for i in range(n)}index_to_city = {i: chr(ord('A') + i) for i in range(n)}if q not in city_to_index:raise ValueError(f"住地城市 {q} 不存在于城市列表中。")q = city_to_index[q]# 初始化距離矩陣，INF 表示兩城市間無直接路徑INF = sys.maxsizedist = [[INF] * n for _ in range(n)]for i in range(n):dist[i][i] = 0for a, b, w in edges:if a not in city_to_index or b not in city_to_index:raise ValueError(f"城市 {a} 或 {b} 不存在于城市列表中。")dist[city_to_index[a]][city_to_index[b]] = w# 動態規劃表dp = [[INF] * n for _ in range(1 << n)]dp[1 << q][q] = 0# 遍歷所有狀態for mask in range(1 << n):for i in range(n):if mask & (1 << i):for j in range(n):if not mask & (1 << j):dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])# 尋找最小花費min_cost = INFfor i in range(n):if i != q:min_cost = min(min_cost, dp[(1 << n) - 1][i] + dist[i][q])# 找到所有最小花費的路徑def find_paths(mask, i):if mask == (1 << q):return [[index_to_city[i]]]paths = []for j in range(n):if mask & (1 << j) and dp[mask][i] == dp[mask ^ (1 << i)][j] + dist[j][i]:for path in find_paths(mask ^ (1 << i), j):paths.append(path + [index_to_city[i]])return pathsresult_paths = []for i in range(n):if i != q and dp[(1 << n) - 1][i] + dist[i][q] == min_cost:for path in find_paths((1 << n) - 1, i):result_paths.append(path)result_paths = sorted(result_paths)return min_cost, result_paths# 輸入處理
n, m, q = input().split()
n = int(n)
m = int(m)edges = []
for _ in range(m):a, b, w = input().split()w = int(w)edges.append((a, b, w))min_cost, result_paths = tsp(n, m, q, edges)# 輸出結果
print(f"最小花費是{min_cost}")
print(f"最小花費共有{len(result_paths)}種方案,分別是:")
for path in result_paths:print(" ".join(path))