2100年，宇宙傳輸將會成為事實。宇宙傳輸公司計畫了一些航班在一些人潮洶湧的行星上。
這些航班的花費已經預先決定了，而花費的單位叫做「嘎洛洛」。
對一些沒有直接航班的行星間而言，他們可以選擇一些直接航班可到之處當作中繼站(ex: A-B, B-C，那麼A可以到C)。
為了協助旅客們查詢航班，宇宙傳輸公司想要提供一個軟體讓旅客們可以直接找到最好的方式(花費最少的方式)從某星球到某星球，
輸出最好路徑上所有點。而如果有兩種以上的最好方法的話，就選擇編號較小的星球。
每個測試資料保證只有一個最好路徑。
技術規格
第一行有兩個整數s, p，中間空一空白。s代表星球數，p代表直接連線數。
接下來一行有一個整數n(n <= 20)表示有多少個問題。
接下來的n行，每一行包含兩個字每ek和em，表示使用者正在找的最便宜的方式從星球ek到em。
對每個詢問，輸出一行最好的路徑，起點、中繼點以及終點，每個點之間空一個空白格。