1 #include <iostream>
  2 #include <queue>
  3 #include <string.h>
  4 
  5 using namespace std;
  6 
  7 struct edge
  8 {
  9     int    zhongdian, changdu;
 10     int    next = 0;
 11 };
 12 
 13 int first[2333];
 14 
 15 edge ed[200005];
 16 
 17 int n, m, en;
 18 
 19 void add_edge( int s, int e, int d )
 20 {
 21     en++;
 22     ed[en].next        = first[s];
 23     first[s]        = en;
 24     ed[en].zhongdian    = e;
 25     ed[en].changdu        = d;
 26 }
 27 
 28 
 29 const int    MAXN    = 100010;
 30 const int    INF    = 0x3f3f3f3f;
 31 int        dist[MAXN];
 32 
 33 bool use[MAXN];
 34 
 35 struct rec
 36 {
 37     int p, dist;
 38 
 39     rec()
 40     {
 41     }
 42     rec( int a, int b )
 43 
 44     {
 45         p = a, dist = b;
 46     }
 47 };
 48 
 49 bool operator < (const rec &a, const rec &b)
 50 
 51 {
 52     return(a.dist > b.dist);
 53 }
 54 
 55 priority_queue<rec> heap;
 56 
 57 void dijkstra_heap()
 58 
 59 {
 60     memset( dist, 0x3f3f, sizeof(dist) );
 61 
 62     dist[1] = 1;
 63     for ( int a = 1; a <= n; a++ )
 64     {
 65         heap.push( rec( a, dist[a] ) );
 66     }
 67     for ( int a = 1; a <= n; a++ )
 68     {
 69         while ( use[heap.top().p] )
 70         {
 71             heap.pop();
 72         }
 73         rec now = heap.top();
 74         heap.pop();
 75         int p = now.p;
 76         use[p] = true;
 77         for ( int i = first[p]; i; i = ed[i].next )
 78         {
 79             if ( dist[p] * ed[i].changdu < dist[ed[i].zhongdian] )
 80 
 81             {
 82                 dist[ed[i].zhongdian] = (dist[p] * ed[i].changdu) % 9987;
 83                 if ( dist[ed[i].zhongdian] == 0 )
 84                 {
 85                     dist[ed[i].zhongdian] = 9987;
 86                 }
 87                 heap.push( rec( ed[i].zhongdian, dist[ed[i].zhongdian] ) );
 88             }
 89         }
 90     }
 91 }
 92 
 93 
 94 int main()
 95 {
 96     cin >> n >> m;
 97     for ( int a = 1; a <= m; a++ )
 98     {
 99         int s, e, d;
100         cin >> s >> e >> d;
101         add_edge( s, e, d );
102         add_edge( e, s, d );
103     }
104     dijkstra_heap();
105     cout << dist[n] << endl;
106     return(0);
107 }