题目描述

给定一张有向图，顶点编号为 $0,1,\ldots,n$。你需要从顶点 $0$ 出发，到达顶点 $n$。

图中有 $m$ 条有向边，第 $i$ 条边从 $a_i$ 指向 $b_i$，长度为 $c_i$。保证：

• 对任意边都有 $a_i<b_i$，因此图中不存在有向环；
• 不存在两条边 $i,j$ 满足 $a_i<a_j<b_i<b_j$。

顶点 $1,2,\ldots,n-1$ 各有一种颜色，第 $i$ 个中间顶点的颜色记为 $color_i$。

对于每一种颜色，你必须满足：要么经过这种颜色的所有顶点，要么一个也不经过。也就是说，如果两个中间顶点颜色相同，那么所选路径必须同时经过它们，或同时不经过它们。

请找出从 $0$ 到 $n$ 的合法路径的最小总长度。如果不存在合法路径，输出 $-1$。

输入格式

第一行两个整数 $n,m$，表示终点编号为 $n$，以及边数。

接下来 $m$ 行，每行三个整数 $a_i,b_i,c_i$，表示一条从 $a_i$ 到 $b_i$、长度为 $c_i$ 的有向边。

最后一行包含 $n-1$ 个整数 $color_1,color_2,\ldots,color_{n-1}$，其中 $color_i$ 表示顶点 $i$ 的颜色。

输出格式

输出一个整数，表示合法路径的最小总长度。如果不存在合法路径，输出 $-1$。

样例输入

3 4
0 1 10
0 2 10
1 2 10
2 3 10
1 2

样例输出

20

数据范围

• $2\le n\le 1000$；
• $1\le m\le 1000$；
• $0\le a_i<b_i\le n$；
• $1\le c_i\le 10^6$；
• $1\le color_i\le 1000$；
• 不存在 $i,j$ 使得 $a_i<a_j<b_i<b_j$。