Migrated from Lutece 1147 秋实大哥带我飞

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

然而题目和题面并没有什么关系。

给出$n$个点，$m$条带权无向边，问你从$1$号点到$n$号点的最短路中有多少种走法？

Input

第一行两个数$n$,$m$分别表示点的个数和边的个数。 （$2\leq n\leq 2000$，$1\leq m\leq2000$）

接下来$m$行，每行3个数$u$,$v$,$w$表示$u$号点到$v$号点有一条距离为$w$的边。（$1\leq u,v\leq n$，$0\leq w\leq 100000$）

数据保证$1$号点能够到达$n$号点，点和边都可以被走多次。

Output

如果有无穷种走法，输出-1。否则输出走法的方案数mod 1000000009。

Samples

4 4
1 2 1
1 3 1
2 4 1
3 4 1

2

4 4
1 2 1
1 3 1
2 4 1
3 4 0

-1

Resources

2015 UESTC Training for Graph Theory