• A
• B
• C
• D
• E
• F
• G
• H
• I
• J
• K
• L
• M
• N
• O
• P
• Q
• R
• S
• T
• U
• V
• W
• X
• Y
• Z
• AA
• AB
• AC
• AD
• AE
• AF
• AG
• AH
• AI
• AJ
• AK
• AL
• AM
• AN
• AO
• AP
• AQ
• AR
• AS
• AT
• AU
• AV
• AW

寻找最少费用 3115

Description

暑假来临，BoBoo文打算通过做家教的方式赚取生活费，去目的地的途中需要经过若干个城市。

如图所示，带箭头的边表示公交车行驶方向，上面的数字表示两城市间通行所需的费用。

BoBoo文从 A 城市到 H 城市的乘车路线可以选择“A->D->G->H”,

也可以选择“A->E->F->H”,

还可以选择“A->B->C->H”等.

其中“A->E->F->H”为所有路线中的所需花费最少的方案，总费用为 30(12+3+5+10)。

BoBoo文家在A点，目的地为H点，线路固定，但是每段路线的费用不固定。

由于BoBoo文不擅长规划，但又不想把钱浪费在路费上，

请你帮助BoBoo文找到在某一路线方案费用的情况下从A城市到H城市花费最少费用的乘车方案以及最少费用。

（最少费用唯一）

Input

城市A、B、C、D、E、F、G、H 分别编号为 0一7。

路线图以若干行a b c形式的数据给出。

其中a，b，c分别表示从a城市到b城市所需费用为c元。( $ 1\leq c \leq 1e12 $)

数据保证可以从起点0到达终点7

Output

第一行输出BoBoo文从家到目的地的路线（用->相连，包括起点和终点）

第二行表示最小费用

Samples