Minimum Distance

You are given a directed graph with edge weights, which are (large) powers of 2. We need to calculate the minimum distance from vertex S to vertex T. Since this distance can be a very large number, we are asked to compute the remainder of the integer division (modulo) of the distance by the number 10~^9~ + 7.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the edges of the graph and the vertices S and T, and finds the remainder of the integer division (modulo) of the minimum distance from S to T by the number 10~^9~ + 7.

Input Files:

The input file named shortpowtwo.in is a text file. The first line contains two integers N and M, separated by a single space: the number of vertices and the number of edges of the graph, respectively. Each of the next M lines describes an edge: it contains three integers u, v, and w separated in pairs by a single space, which means that there is an edge from vertex with number u to vertex with number v, with weight 2~^w~. Vertices are numbered from 1 to N. The next and last line contains two integers S and T, separated by a single space: the numbers of the starting and destination vertices, respectively.

Output Files:

The output file named shortpowtwo.out is a text file consisting of only one line containing exactly one integer: the remainder of the integer division (modulo) of the minimum distance from vertex S to vertex T by the number 10~^9~ + 7. If there is no path from vertex S to vertex T, this line must contain the number -1.

Examples of input - output files:

1ο

STDIN (shortpowtwo.in)

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

STDOUT (shortpowtwo.out)

3

2o

STDIN (shortpowtwo.in)

4 3
1 2 4
2 3 5
3 4 6
1 4

STDOUT (shortpowtwo.out)

112

3ο

STDIN (shortpowtwo.in)

4 2
1 2 0
3 4 1
1 4

STDOUT (shortpowtwo.out)

-1

Constraints:

• For test cases worth 20% of the total points, it will be:
  1 ~\le~ Ν ~\le~ 1000, 0 ~\le~ Μ ~\le~ 1000, 0 ~\le~ w ~\le~ 10
• For test cases worth 40% of the total points, it will be:
  1 ~\le~ Ν ~\le~ 100.000, 0 ~\le~ Μ ~\le~ 100.000, 0 ~\le~ w ~\le~ 10
• For test cases worth 65% of the total points, it will be:
  1 ~\le~ Ν ~\le~ 100.000, 0 ~\le~ Μ ~\le~ 100.000, 0 ~\le~ w ~\le~ 500
• For test cases worth 100% of the total points, it will be:
  1 ~\le~ Ν ~\le~ 100.000, 0 ~\le~ Μ ~\le~ 100.000, 0 ~\le~ w ~\le~ 100.000

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 2 sec.
Maximum available memory: 256 MB.