Country in Distortion

D: Country In Distortion-

story

Alice was completely bored. This is because the White Rabbit, who is always playing with him, is out to Trump Castle. (Ah, I wish I had gone out with him in this case.) Alice thought. However, this is a country of distortion. If you go out so easily, you will get very tired. What does that mean?

The white rabbit was in trouble. On the way to Trump Castle, I made a slight mistake. (I'm in trouble. Let's go back and ask Alice, who knows the way well, to guide us.) The White Rabbit thought. Even so, the white rabbit seems to be very tired. The white rabbit looks at the pocket watch

"Why does the road in this country feel like the length has changed every time I pass it! I felt that this road was about 100 meters a while ago, but this time it's about 1 km? The time it takes hasn't changed much! "

Screaming. Yes, this is a country of distortion. It is truly a mysterious country where the roads continue to distort from moment to moment. The white rabbit that finally arrived at Alice's house was the first to open.

"I'm sorry Alice. Can you give me directions to Trump Castle?"

Speaking of which, Alice, who was bored and prostrated off ton, jumped up energetically.

"Of course! Let's go together!"

On the other hand, Alice, looking at the tired white rabbit (but it's bad to be too tired), took out a map of the distorted country from the back of the house.

"Now, I'm looking for a tireless way to Trump Castle!"

problem

An undirected graph consisting of n vertices and m edges is given. The time required to move each side i is represented by t_i. In addition, v_0 is given as the initial perceived movement speed. After that, the perceived movement speed changes each time it passes through one side. The perceived movement speed after passing through j sides is given by the following formula with integers a, b, and c as parameters.

v_j = (a \ times v_ {j-1} + b) mod c

When passing through side i at speed v_j, the perceived movement distance becomes t_i \ times v_j. In a country of distortion, it is possible to move even if the perceived movement speed is 0, and the perceived movement distance at that time is 0.

Now consider a path that starts at vertex 1 and returns to vertex 1 via vertex n. Minimize the sum of the perceived travel distances in the possible routes.

Input format

n m x_1 y_1 t_1 ... x_m y_m t_m v_0 a b c

All inputs consist of integers. In the first line, n and m representing the number of vertices and sides of the graph are given in this order, separated by blanks. In the i-th line of the following m lines, the two vertices x_i and y_i to which the i-th side connects and the time t_i required to pass are given in this order, separated by blanks. The second line of m + is given v_0, which represents the initial velocity. On the m + 3rd line, the parameters a, b, and c of the velocity calculation formula are given in this order, separated by blanks.

Constraint

• Each value is an integer.
• 2 \ leq n \ leq 500
• 1 \ leq m \ leq min \ {5000, n (n -1) / 2 \}
• For each i = 1, ..., m 1 \ leq x_i <y_i \ leq n. Also, for i and j that satisfy 1 \ leq i <j \ leq m, x_i \ neq x_j or y_i \ neq y_j. That is, there are no self-loops and multiple edges.
• For each i = 1, ..., m 1 \ leq t_i \ leq 10 ^ 8
• 0 \ leq v_0 \ leq 49
• 0 <a <c, 0 \ leq b <c, v_0 <c \ leq 50
• The graph is concatenated. That is, it is guaranteed that there is a path between any two vertices.

Output format

Output the minimum value of the sum of the perceived movement distances on one line.

Input example 1

4 4 one two Three 2 3 1 2 4 5 3 4 2 Five 4 5 6

Output example 1

34

Input example 2

6 5 1 2 1 2 3 100 3 4 2 4 5 200 5 6 1 3 4 5 9

Output example 2

341

Before passing through the sides (2,3) and (4,5), which take a long time to pass, it is better to make a round trip on the road that can be passed in a short time and slow down as much as possible.

Input example 3

10 9 1 2 74150933 2 3 13214145 3 4 45636411 4 5 90778512 5 6 85676138 6 7 60913535 7 8 43917556 8 9 47519690 9 10 56593754 33 37 41 47

Output example 3

23049391759

The perceived movement distance may be very long.

Example

Input

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

Output

34

inputFormat

Input format

n m x_1 y_1 t_1 ... x_m y_m t_m v_0 a b c

All inputs consist of integers. In the first line, n and m representing the number of vertices and sides of the graph are given in this order, separated by blanks. In the i-th line of the following m lines, the two vertices x_i and y_i to which the i-th side connects and the time t_i required to pass are given in this order, separated by blanks. The second line of m + is given v_0, which represents the initial velocity. On the m + 3rd line, the parameters a, b, and c of the velocity calculation formula are given in this order, separated by blanks.

Constraint

• Each value is an integer.
• 2 \ leq n \ leq 500
• 1 \ leq m \ leq min \ {5000, n (n -1) / 2 \}
• For each i = 1, ..., m 1 \ leq x_i <y_i \ leq n. Also, for i and j that satisfy 1 \ leq i <j \ leq m, x_i \ neq x_j or y_i \ neq y_j. That is, there are no self-loops and multiple edges.
• For each i = 1, ..., m 1 \ leq t_i \ leq 10 ^ 8
• 0 \ leq v_0 \ leq 49
• 0 <a <c, 0 \ leq b <c, v_0 <c \ leq 50
• The graph is concatenated. That is, it is guaranteed that there is a path between any two vertices.

outputFormat

Output format

Output the minimum value of the sum of the perceived movement distances on one line.

Input example 1

4 4 one two Three 2 3 1 2 4 5 3 4 2 Five 4 5 6

Output example 1

34

Input example 2

6 5 1 2 1 2 3 100 3 4 2 4 5 200 5 6 1 3 4 5 9

Output example 2

341

Before passing through the sides (2,3) and (4,5), which take a long time to pass, it is better to make a round trip on the road that can be passed in a short time and slow down as much as possible.

Input example 3

10 9 1 2 74150933 2 3 13214145 3 4 45636411 4 5 90778512 5 6 85676138 6 7 60913535 7 8 43917556 8 9 47519690 9 10 56593754 33 37 41 47

Output example 3

23049391759

The perceived movement distance may be very long.

Example

Input

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

Output

34

样例

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

34