U530478 开往W城的特快(The express train to city W)

小福家住在A城，他在W城有个朋友。小福想去W城拜访他的朋友，他准备坐特快去W城，他想让去W城的总用时最短。(两趟特快之间的换乘时间为15分钟，中间会经过B，C，D，E，F城的其中之一，或两个城市，三个城市，四个城市）

每一趟特快都是往返的，即A B 33指从A城到B城和从B城到A城都是33分钟。

每一行都是这些特快的参数(始发城市，到达城市，所需时间)，各参数之间以一个空格隔开。

两行，第一行是最短时间，第二行表示怎么去W城(具体参见样例)

数据保证，任意两城之间的所需时间大于0且小于1000。