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$。