oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

towerdefense Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

towerdefense.html

Ook the Oktopus is addicted to a new game -- Bloons Tower Defense. Ook wants to protect his castle from the bloons with his 3 amazing attacks: he can smash the bloons with his Oktopus legs, squirt ink at bloons to slow them down (bloons can't move if they can't see where they're going), or shoot at bloons with LaZ0r eyes. Between Ook's castle and the bloons' camp, there is some multidimensional hyperspace with N-2 nodes (numbered from 1 to N-2), and E hyperspace tunnels. The existence of a (1-directional) hyperspace tunnel between node A and B means that bloons need to travel some positive distance C to get from A to B if they use that tunnel. There could possibly be more than 1 tunnel joining any pair of nodes A and B. Ook's castle is at node N-1 and the bloons' camp is at node 0.

However, Ook is easily distracted. If the bloons move in too many directions at once, Ook will be distracted and unable to defend his castle from the bloons. Fortunately, Ook has spies all over the bloons camp and knows some insider information. From his uber-secret spying on bloons, Ook knows that bloons don't have legs and actually need quite a lot of air power to move. The bloons are quite lazy and will always take the shortest path possible between any two points.

Ook will like to know how many different paths the bloons can take from their camp to attack his castle so that he can defend it most effectively. However, Ook can't count because he is quite short-sighted. Can you help Ook?

Input

The first line contains 2 numbers, N and E.

The next E lines contain 3 numbers, A, B and C, which indicates there is a tunnel from A to B with distance C.

Output

Output 1 line with the number of ways mod 1000000007 the bloons can get from their camp to Ook's castle.

Constraints

For all subtasks, 1 < N ≤ 100,000, 1 ≤ E ≤ 500,000, 0 ≤ A,B ≤ N, 0 < C ≤ 1000.

Subtask 1 (7%): There is at most 1 tunnel starting from each node.

Subtask 2 (11%): 3 ≤ N ≤ 100,000. There are exactly N-2 tunnels starting from node 0, and exactly 1 tunnel ends at each node between nodes 1 to N-2. There is exactly 1 tunnel starting at each of the nodes numbered from 1 to N-2 and ending at node N-1.

Subtask 3 (29%): 1 < N ≤ 500.

Subtask 4 (17%): There are no cycles in the graph.

Subtask 5 (36%): No further constraints.

Sample Input

5 5
0 1 10
1 2 2
1 3 3
2 4 3
3 4 2

Sample Output

2

Explanation: there are 2 possible ways for the bloons to go from 0 to 4. (0 → 1 → 2 → 4 and 0 → 1 → 3 → 4)

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
17141s32MBMinimum
211141s32MBMinimum
329211s32MBMinimum
41761s32MBMinimum
536151s32MBMinimum
6011s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o towerdefense -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.