#215981. [TOPC 2024] Lexicopolis

Welcome to Lexicopolis, the ancient city of legends and treasures. The city is famous for its intricate network of one-way roads. There are intersections and one-way roads connecting the intersections. People can only travel from intersection to intersection along road , and road is associated with a magical number . A path of length from intersection to is a sequence of roads that allows travel from intersection to intersection . A path is lexicographically smaller than another path if at the first road where they have different magic numbers (not index), the number on the first path is smaller than the number on the second path.

It is rumored that the tourist who figures out the lexicographically smallest path of length from intersection to intersection can receive a gift from the Lexicopolis government. Please write a program to find the lexicographically smallest path of length from intersection to . If it is impossible to travel from intersection to with exactly roads, output .

The first line contains six integers . is the number of intersections. is the number of roads. is the starting intersection and is the ending intersection. is a number that will be used for outputting the answer. is the length of path. The -th of the following lines contains three integers , and . That means road is from intersection to intersection and associated with magic number .

If there is no path of length from intersection to , output -1. Otherwise, assume such a path exists. Consider the lexicographically smallest path , and output modulo , where is the number provided as the fifth value in the first line of the input.

样例输入 1

3 6 1 3 10 4
1 2 2
2 1 1
1 3 1
3 1 2
2 3 1
3 2 2

样例输出 1

1211

样例输入 2

3 6 1 3 10 5
1 2 2
2 1 1
1 3 1
3 1 2
2 3 1
3 2 2

样例输出 2

12121

样例输入 3

6 7 5 6 10 10
1 2 1
2 4 2
3 4 1
4 5 3
5 3 5
4 6 2
6 5 1

样例输出 3

121513477

样例输入 4

6 7 1 6 123 2
1 2 1000000000
2 4 2
3 4 3
4 5 4
5 3 1
4 6 2
6 5 1

样例输出 4

-1

• for
• for
• for
• for
• for