34. 朋友相依關係

某社群平台上，每一個使用者都可以將其他使用者設定為【認識的人】，並填上對該使用者的【熟悉度】數值。
若 A 和 B 互相加對方為認識的人，則 A 與 B 的關係為【朋友】，其熟悉度為兩人設定的較小值。
A 可以找尋 B 的朋友，然後認識第二層的新朋友，透過這種方法可以認識一層又一層新的朋友。

給定 N 個認識的人與 A，B，請找出 :
1.  A 最少要經過多少層的朋友關係才能找到 B ? 會經過哪些朋友?
2.  假設 A 要經過加總最大熟悉度的朋友關係才能找尋到 B，則會經過哪些朋友? 加總的最大熟悉度為何?

【輸入說明】
第一行：輸入N個整數，代表認識的人 (2<=N<=10)
第二行：輸入兩個字元(X,Y)和一個數值(K)，中間皆用一個空白隔開，分別代表第一個人，第二個人，以及第一個人對第二個人的熟悉度(1<=K<=10)。
…
直到輸入 -1 結束

範例輸入說明:
3 (總共有3個人，A，B，C)
A B 3 (A 認識 B，熟悉度為 3，中間皆用一個空白隔開)
B A 4 (B 認識 A，熟悉度為 4，中間皆用一個空白隔開)
A C 2 (A 認識 C，熟悉度為 2，中間皆用一個空白隔開)
C A 3 (C 認識 A，熟悉度為 3，中間皆用一個空白隔開)
C B 3 (C 認識 B，熟悉度為 3，中間皆用一個空白隔開)
B C 5 (B 認識 C，熟悉度為 5，中間皆用一個空白隔開)
-1 (結束)

【輸出說明】
第一行：輸出 A 經過多少層找到 B
第二行：輸出 A 經過哪些朋友找到 B (包括起點A和終點B)，朋友之間用一個空白隔開
第三行：輸出 A 找到 B 所經過的最大熟悉度加總
第四行：輸出 A 經過哪些朋友找到 B (包括起點A和終點B)﹐朋友之間用一個空白隔開

範例輸出說明:
1 (A 僅需經過 1 層朋友關係即可認識 B (A 和 B 原本就認識))
A B (A 和 B 原本就認識，不需經過其他朋友，朋友之間用一個空白隔開)
5 (加總的最大熟悉度為 5)
A C B (A 認識 C 後再透過 C 認識 B，朋友之間用一個空白隔開)

因為A對C的熟悉度為2，C對A的熟悉度為3，所以A與C之間的熟悉度為2(取較小值)
因為C對B的熟悉度為3，B對C的熟悉度為5，所以B與C之間的熟悉度為3(取較小值)
當 A 認識 C，再透過 C 認識 B，會得到加總最大的熟悉度 2 + 3 = 5。

【特殊要求】
請使用 dictionary 儲存資料並完成此題目

【測試資料一】
輸入：
3
A B 3
B A 4
A C 2
C A 3
C B 3
B C 4
-1

輸出：
1
A B
5
A C B


【測試資料二】
輸入：
5
C A 3
A C 1
B C 8
C B 6
D E 1
E D 2
E B 1
B E 3
-1

輸出：
2
A C B
7
A C B

【測試資料三】
輸入：
7
A C 2
C A 8
A E 6
E A 8
C D 1
D C 8
E F 4
F E 9
B D 4
D B 3
F G 2
G F 4
B G 4
G B 5
-1

輸出：
3
A C D B
16
A E F G B

【測試資料四】
輸入：
6
A E 2
E A 1
E C 2
C E 1
D C 2
C D 1
B D 2
D B 1
A F 2
F A 1
E F 2
F E 1
-1

輸出：
4
A E C D B
5
A F E C D B


【隱藏測試資料一】
輸入：
5
A B 3
B A 4
A D 2
D A 3
B D 4
D B 5
B C 2
C B 6
C D 3
D C 4
D E 3
E D 8
-1

輸出：
1
A B
7
A D C B

【隱藏測試資料二】
輸入：
5
D A 5
A D 3
A C 1
C A 2
D C 7
C D 9
D B 2
B D 5
E C 7
C E 3
-1

輸出：
2
A D B
10
A C D B

【隱藏測試資料三】
輸入：
6
A E 3
E A 4
C A 9
A C 6
D E 5
E D 2
C F 1
F C 3
B D 2
D B 1
E C 4
C E 6
-1

輸出：
3
A E D B
13
A C E D B

【隱藏測試資料四】
輸入：
5
A E 2
E A 1
E C 2
C E 1
D C 2
C D 1
B D 2
D B 1
-1

輸出：
4
A E C D B
4
A E C D B