AT_wupc2019_f RPG

卡托正在制作某个RPG的剧本。这个RPG有N个场面，各场面已经决定是“战斗”还是“空地”。另外，有连接M个场景之间的移动通道，第i个通道可以从场景ai移动到场景bi。最初，作为RPG的主人公的辛亚，在场面1中，自由地在通道上移动，到达场面N后游戏就完成了。 辛亚有“精神”和“疲劳”两种状态。在“精神”状态下可以战斗，但在“疲劳”状态下不能战斗。在“疲劳”状态下去“战斗”场面的话，游戏就结束了。 辛亚以“精神”状态开始游戏。当你通过“战斗”场面时，你会累得处于“疲劳”状态。为了从“疲劳”状态回到“精神”状态，需要通过“恢复所”。 “恢复所”可以设置在任何“空地”场景中。在场景\\\（2\leqi\leq N-1）\中设置恢复点的成本是ci。 现在，还没有决定在哪里设置“恢复所”。因此，卡托决定设置“恢复所”，以满足以下条件。 > * 无论从场面\（1\）开始行动的辛雅选择了怎样的移动，从任意的“战斗”场面到达其他的“战斗”场面之间，至少有一次通过“恢复所”。 > * 游戏通关时的辛亚的状态可以是“疲劳”也可以是“精神”。 为了满足以上条件，请求出卡托设置“恢复所”时所需成本合计的最小值。如果如何设置“恢复站”都不能满足条件，请输出-1。

输入以以下形式由标准输入给出。 N M c2 c3 dots c{N-1} a_1 b_1 a_2 b_2 vdots a_M b_M

请输出符合条件的“恢复站”安装成本合计的最小值。如果无法满足条件，请输出-1。

·\(3 \leq N \leq 500\) ·\(N-1 \leq M \leq 1000\) ·\(-1 \leq c_i \leq 10^9 \ (2 \leq i \leq N-1)\) ·\（c_i=-1\）那么，场面\（i\）就是“战斗”场面。 ·\（c_i\geq0\）那么，场景\（i\）是“空地”场景，在那里设置“休息处”的成本是\（c_i\）。 ·\(1 \leq a_i , b_i \leq N \ (1 \leq i \leq M)\) ·表示存在从场景ai到场景bi的移动通路。 ·N当视为顶点M边的有向曲线时，所有顶点都存在来自顶点1的路径和朝向顶点N的路径。另外，不存在闭路。 ·输入的值都是整数。 ### 样例解释1 最适合选择场景3和场景5。 ### 样例解释2 无法在场景2到场景3之间设置“恢复站”。