Lexicopolis

Lexicopolis is an ancient city known for its legends and treasures. The city is known for its tangled network of one-way roads. There are $n$ intersections and $m$ one-way roads. Road $i$ lets people travel only from intersection $u_i$ to intersection $v_i$, and it carries a magic number $w_i$.

A path of length $k$ from $s$ to $t$ is a sequence of roads $e_1, e_2, \dots, e_k$ that can be traveled in order from $s$ to $t$. When two paths are compared, look at the first position where their magic numbers differ. The path with the smaller number at that position is lexicographically smaller. Compare the magic numbers, not the road indices.

A rumor says that a tourist who finds the lexicographically smallest path of length $k$ from $s$ to $t$ receives a gift from the government. Write a program that finds this path.

The first line contains six integers $n$, $m$, $s$, $t$, $x$, and $k$. Here $n$ is the number of intersections, $m$ is the number of roads, $s$ is the starting intersection, $t$ is the destination intersection, $x$ is the base used in the final answer, and $k$ is the path length. Each of the next $m$ lines contains three integers $u_i$, $v_i$, and $w_i$. This means road $i$ goes from $u_i$ to $v_i$ and has magic number $w_i$.

If no path of length $k$ from $s$ to $t$ exists, print -1. Otherwise, take the lexicographically smallest path $e_1, e_2, \dots, e_k$ and print the value of $\sum_{i=1}^{k} w_{e_i} x^{k-i}$ modulo $10^9+7$.

• $2 \le n \le 50$
• $1 \le m \le n^2 - n$
• $1 \le u_i, v_i \le n$, and $u_i \ne v_i$
• $1 \le w_i \le 10^9$
• Each ordered pair $(u_i, v_i)$ appears at most once.
• $1 \le s, t \le n$
• $1 \le k \le 10^9$
• $1 \le x \le 10^9$