1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 const int N = 509;
 5 int g[N][N],dist[N],st[N];
 6 int n,m;
 7 
 8 int dijkstra()
 9 {
10     for(int i = 1;i <= n;++i)
11     {
12         int t = -1;
13         for(int j = 1;j <= n;++j)
14             if(!st[j] && (t == -1 || dist[t] > dist[j]))
15                 t = j;
16         st[t] = 1;
17         for(int j = 1;j <= n;++j)
18             dist[j] = min(dist[j],dist[t] + g[t][j]);
19     }
20     if(dist[n] == 0x3f3f3f3f)
21         return -1;
22     else
23         return dist[n];
24 }
25 
26 int main()
27 {
28     cin >> n >> m;
29     memset(g,0x3f3f3f3f,sizeof g);
30     for(int i = 1;i <= m;++i)
31     {
32         int a,b,c;
33         cin >> a >> b >> c;
34         g[a][b] = min(g[a][b],c);
35     }
36     memset(dist,0x3f3f3f3f,sizeof dist);
37     dist[1] = 0;
38     cout << dijkstra() << endl;
39     return 0;
40 }