{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cp\u003e\u003cimg SRC\u003d\"CDN_BASE_URL/1d5c0a5cd293f6e585de08726e9579e8?v\u003d1539413088\" alt\u003d\"Qiushidage Bring Me Fly\"\u003e\u003c/p\u003e \n \u003cp\u003e然而题目和题面并没有什么关系。\u003c/p\u003e \n \u003cp\u003e给出$n$个点，$m$条带权无向边，问你从$1$号点到$n$号点的最短路中有多少种走法？\u003c/p\u003e \n \u003c/body\u003e\n\u003c/html\u003e\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027],[\u0027\\[\u0027,\u0027\\]\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cp\u003e第一行两个数$n$,$m$分别表示点的个数和边的个数。 \u003cbr\u003e（$2\\leq n\\leq 2000$，$1\\leq m\\leq2000$）\u003c/p\u003e \n \u003cp\u003e接下来$m$行，每行3个数$u$,$v$,$w$表示$u$号点到$v$号点有一条距离为$w$的边。（$1\\leq u,v\\leq n$，$0\\leq w\\leq 100000$）\u003c/p\u003e \n \u003cp\u003e数据保证$1$号点能够到达$n$号点，点和边都可以被走多次。\u003c/p\u003e \n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cp\u003e如果有无穷种走法，输出\u003ccode\u003e-1\u003c/code\u003e。否则输出走法的方案数\u003ccode\u003emod 1000000009\u003c/code\u003e。\u003c/p\u003e \n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e4 4\n1 2 1\n1 3 1\n2 4 1\n3 4 1\u003chr/\u003e4 4\n1 2 1\n1 3 1\n2 4 1\n3 4 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e2\u003chr/\u003e-1\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\u003c/body\u003e\n\u003c/html\u003e"}}]}