> #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 (index[heap[x]], index[heap[smallest]]);
>                        swap (heap[x], heap[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;
>      min = dist[heap[1]];
>      heap[1] = heap[heap_size];
>      index[heap[heap_size]] = 1;
>      heap_size --;
>      min_heapfy (1);
>      return min;
> }
> bool empty ()
> {
>      return heap_size > 0 ? false : true;
> }
> void increase (int i)
> {
>      int j;
>      j = i / 2;
>      while (i >= 1 && j > 0 && dist[heap[i]] < dist[heap[j]])
>      {
>            swap (index[heap[i]], index[heap[j]]);
>            swap (heap[i], heap[j]);
>            i = j;
>            j = i / 2;
>      }
> }
> int Dijkstra (int s)
> {
>      int t, tmp1, tmp2, j, v, w;
>      edge *p;
>      visited[s] = true;
>      while (!empty())
>      {
>          v = heap[1];
>          visited[v] = true;
>          if (v == (n - 1))
>          {
>                return dist[v];
>          }
>          extract_min ();
>          p = ver[v].first;
>          while (p)
>          {
>                if (!visited[p->id])
>                {
>                                    j = p->id;
>                                    w = p->len;
>                                    if (dist[v] + w < dist[j])
>                                    {
>                                                dist[j] = dist[v] + w;
>                                                increase (index[j]);
>                                    }
>                }
>                p = p->next;
>          }
>      }
> }
> 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;
> }
>