> #include <iostream>
> #include <fstream>
> #include <cstdio>
> const int N = 31000;
> 
> using namespace std;
> 
> struct edge
> {
>        int id, len;
>        edge *next;
> };
> struct vertex
> {
>        edge *first;
> };
> 
> vertex ver[N];
> int n, m, heap_size, dist[N], index[N], heap[2*N];
> bool visited[N];
> 
> int left (int i)
> {
>     return 2*i;
> }
> int right (int i)
> {
>     return 2*i + 1;
> }
> int parent (int i)
> {
>     return i/2;
> }
> void swap (int &a, int &b)
> {
>      int t;
>      t = a;
>      a = b;
>      b = t;
> }
> void min_heapfy (int x)
> {
>      int l, r, smallest = x;
>      if (x >= 1 && x <= heap_size)
>      {
>           l = left (x);
>           r = right (x);
>           if (l <= heap_size && dist[heap[l]] < dist[heap[smallest]])
>           {
>                 smallest = l;
>           }
>           if (r <= heap_size && dist[heap[r]] < dist[heap[smallest]])
>           {
>                 smallest = r;
>           }
>           if (smallest != x)
>           {
>                        swap (heap[x], heap[smallest]);
>                        index[heap[x]] = x;
>                        index[heap[smallest]] = smallest;
>                        min_heapfy (smallest);
>           }
>      }
> }
> void build_heap ()
> {
>      int i;
>      for (i = heap_size/2; i >= 1; i --)
>      {
>          min_heapfy (i);
>      }
> }
> int extract_min ()
> {
>      int min = 0;
>      min = dist[heap[1]];
>      heap[1] = heap[heap_size];
>      index[heap[heap_size]] = 1;
>      heap_size --;
>      min_heapfy (1);
>      return min;
> }
> int judge (int x, int y)
> {
>     edge *p;
>     p = ver[x].first;
>     while (p && p->id != y)
>     {
>           p = p->next;
>     }
>     if (p)
>     {
>           return p->len;
>     }
>     else
>     {
>         return -1;
>     }
> }
> bool empty ()
> {
>      return heap_size > 0 ? false : true;
> }
> void fixup (int id)
> {
>      int t1, t2;
>      if (dist[id] < dist[heap[index[id]/2]])
>      {
>                   t1 = index[id]/2;
>                   t2 = heap[index[id]/2];
>                   heap[index[id]] = t2;
>                   index[t2] = index[id];
>                   index[id] = t1;
>                   heap[t1] = id;
>                   fixup (t2);
>      }
> }
> int Dijkstra (int s)
> {
>      int t, tmp1, tmp2, j, v, w;
>      visited[s] = true;
>      while (!empty())
>      {
>          v = heap[1];
>          visited[v] = true;
>          if (v == (n - 1))
>          {
>                return dist[v];
>          }
>          extract_min ();
>          for (j = 0; j < n; j ++)
>          {
>              if (!visited[j])
>              {
>                        w = judge (v, j);
>                        if (dist[v] + w < dist[j] && w != -1)
>                        {
>                                    dist[j] = dist[v] + w;
>                                    fixup (j);
>                        }
>              }
>          }
>      }
> }
> void solve ()
> {
>      int i = 0;
>      heap_size = n - 1;
>      edge *p;
>      p = ver[0].first;
>      while (p)
>      {
>            dist[p->id] = p->len;
>            p = p->next;
>      }
>      dist[0] = 0;
>      build_heap ();
>      printf ("%d\n", Dijkstra (0));
> }
> int main ()
> {
>     int i, a, b, c;
>     edge *p;
>     scanf ("%d %d", &n, &m);
>     for (i = 0; i < n; i ++)
>     {
>         ver[i].first = NULL;
>         visited[i] = false;
>         heap[i] = i;
>         index[i] = i;
>         dist[i] = INT_MAX;
>     }
>     for (i = 0; i < m; i ++)
>     {
>         scanf ("%d %d %d", &a, &b, &c);
>         p = new edge;
>         p->id = b - 1;
>         p->len = c;
>         p->next = ver[a - 1].first;
>         ver[a - 1].first = p;
>     }
>     solve ();
>     
>     return 0;
> }
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
>