1073: 【模板】最短路（1）
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：298
Solved：117
Description
给定一个$n$个点、$m$条边的有向图，要求计算出点$1$到点$n$的最短距离。
Input
第一行：两个整数$n,m$。（$1 \le n \le 10^3$，$1 \le m \le 10^5$）
接下来$m$行：每行三个整数$u_i,v_i,w_i$，表示存在一条从$u_i$到$v_i$，权值为$w_i$的有向边。（$1 \le u_i,v_i \le n$，$1 \le w_i \le 10^6$）
可能存在重边和自环。
接下来$m$行：每行三个整数$u_i,v_i,w_i$，表示存在一条从$u_i$到$v_i$，权值为$w_i$的有向边。（$1 \le u_i,v_i \le n$，$1 \le w_i \le 10^6$）
可能存在重边和自环。
Output
一个整数，表示点$1$到点$n$的最短距离；若不存在从点$1$到点$n$的路径，则输出$-1$。
Sample Input Copy
3 3
1 2 5
2 3 2
1 3 10Sample Output Copy
7