AT_joisc2007_route.象使い (Route)

在平面直角坐标系上有 $n$ 个点和 $m$ 条线段。第 $i$ 条线段连接点 $a_i$ 和点 $b_i$，所需通过时间为 $c_i$。

你需要从 $1$ 号点走到 $2$ 号点。在走线段时，必须从一个端点走到另一个端点（即不考虑相交），且在每次拐弯的时候，拐角不能是锐角。

请求出最少所需时间。

第一行输入点数 $n$ 和边数 $m$。

第二行到第 $(n+1)$ 行，第 $(i+1)$ 行两个整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

第 $(n+2)$ 行到第 $(n+m+1)$ 行，第 $(n+j+1)$ 行输入三个整数 $a_j,b_j,c_j$，表示第 $i$ 条线段连接的两个点的编号及所需时间。

一行一个整数。

• 若可到达，输出最少所需时间；
• 否则，输出 $-1$。

输入输出样例

输入 #1

5 6
0 0
10 10
0 10
10 0
2 -6
1 2 30
1 3 4
1 4 5
1 5 1
2 4 3
2 5 1

输出 #1

8

样例 #1 解释

路径为 $1\to 4\to 2$。

数据规模与约定

对于全部测试点，保证 $1\le n\le 100$，图中无重边，$1\le a_j\lt b_j\le n$，$1\le c_j\le 10000$。