请问是否需要使用高精度？

最短乘积路

时间空间限制：1s,128mb

题目描述

给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。

输入格式

第一行读入两个整数n，m，表示共n个点m条边。

接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。

输出格式

输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此输出它模9987的余数即可。

样例数据

输入

3 3

1 2 3

2 3 3

1 3 10

输出

9

备注

对于20%的数据，n≤10。

对于100%的数据，n≤1000，m≤1000000。

边权不超过10000。