1247 - Interstar Transport

到了西元 2100 年，對於銀河系上的太空旅行已經實現了，星際旅行社打算規劃星球旅行，將兩個最受歡迎的星球設計路線，這路線的花費使用 Galaro 為貨幣單位，並且也出了許多不同語言版本，然而並不是任兩個星球都有被規劃路線，兩個星球間的旅行被限制於太空旅行清單中。

幫助旅客規劃他們的行程，星際旅行社想要提供一款行動 App 找到最佳旅行選擇，最加取決於兩個星球間的旅程花費， 給定起點與終點星球，找到一條路徑有最少花費，並且輸出路程中的每一個星球，如果有同一條路具有相同花費時，則找中間經過最少個星球為最佳路徑。每組測資只會存在一組最佳路徑。

條件限制

1. 星球個數 s (1 <= s <= 26)，且每個星球使用大寫英文字母表示 'A', 'B', 'C', ..., 'Z'。
2. 星球間，最多存在 200 條可進行太空旅行的直通道路。
3. 每條路線的花費都是一個正整數小於等於 100。

Input

輸入第一行會有兩個整數 s, p。
接下來會有 p 行，每行上有兩個字元 e_i , e_j 以及一個整數 d_ij
表示 e_i , e_j  間可以進行太空旅行，且花費為 d_ij，
緊接著會有一個整數 n (1 <= n <= 20)，表示有多少組詢問，
接下來會有 n 行，每行上有兩個字元 e_k , e_m，表示要求這兩個星球的最少花費路徑。

Output

對於每組詢問輸出一行，每個星球編號間以空白隔開，順序為從起點到終點從左至右輸出。

Sample Input

5 7 
A B 1
B C 2
C D 3
D E 2
E A 1
A D 3
A C 4
3 
B D 
A D 
E C

Sample Output

B A D 
A D 
E A B C