最短路

题目背景

狗哥做烂了最短路,突然机智的考了 Bosh 一道,没想到把 Bosh 考住了...你能帮 Bosh 解决吗?

题目描述

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

输入输出格式

输入格式


第一行读入两个整数 $n$,$m$,表示共 $n$ 个点 $m$ 条边。 接下来 $m$ 行,每行三个正整数 $x$,$y$,$z$,表示点 $x$ 到点 $y$ 有一条边权为z的边。

输出格式


输出仅包括一行,记为所求路径的边权之积,由于答案可能很大,因此狗哥仁慈地让你输出它模 $9987$ 的余数即可。 废话当然是一个数了w //谢fyszzhouzj指正w

输入输出样例

输入样例 #1

3 3
1 2 3 
2 3 3 
1 3 10

输出样例 #1

9

说明

对于 $20\%$ 的数据,$n\leq 10$。 对于 $100\%$ 的数据,$n\leq 10^3$,$m\leq 10^6$。边权不超过 $10^4$。