有一个 个点 条边构成的无向图 ，第 条边 有一个颜色 。现在有一个环形颜色圆盘，其包含了编号 的颜色，圆盘上有一个指针，初始指向颜色 ，若指针指向颜色 ，则可以花费 的代价将其指向 或 。 第 个点有一个颜色偏转值 。当你想走过边 时： 若从点 走向点 ，那你在点 时圆盘的指针必须指向 ， 若从点 走向点 ，那你在点 时圆盘的指针必须指向 。 注意，经过边时不能调整指针。 求从点 到点 的最小代价，不可达输出 。

输入描述:

第一行输入三个整数 。第二行输入 个整数 ，表示第 个点的颜色偏转值。接下来 行，第 行输入三个整数 ，表示第 条边双向连接点 和点 ，颜色为 。图可能不连通、可能存在重边。不存在自环。

输出描述:

若点 无法到达点 ，输出 ；否则，输出一个整数，表示从点 到点 的最小代价。