Problem Background

Even a single small light, when gathered together, should become a very mysterious and powerful force.

Nagisa's passing, Sio's departure... Tomoya's life has almost plunged into darkness.

But, will this be the end?

Problem Description

The town of Hikarizaka is represented by a graph consisting of $n$ nodes (numbered from $1$ to $n$) and $m$ directed edges. Each node contains a light orb, and there are $k$ types of light orbs, numbered from $0$ to $k-1$.

To change everything, Tomoya needs to collect all $k$ types of light orbs. He can start from any node and travel freely through the graph, but he will not pass through the same node twice. Each time he encounters a light orb, he will collect it. After collecting $k$ light orbs, i.e., after passing through $k$ nodes, he will stop collecting. Design a plan that allows Tomoya to collect all $k$ types of light orbs with the shortest path length.

In other words, each node has a color, and you need to find the shortest path that visits exactly $k$ nodes and includes all $k$ colors. You are required to output the length of this path.

Input Format

The first line contains three positive integers $n$, $m$, and $k$, representing the number of nodes, the number of edges, and the number of types of light orbs, respectively.

The second line contains $n$ positive integers $a_1$ to $a_n$, where $a_i$ represents the type of light orb at node $i$.

The next $m$ lines each contain three positive integers $u_i$, $v_i$, and $w_i$, indicating that there is a directed edge from $u_i$ to $v_i$ with a length of $w_i$.

Output Format

Output one line. If there is a solution, output a positive integer representing the length of the shortest path that meets the conditions. If there is no solution, output "Ushio!" (without quotes).

Sample Input and Output

Sample Input #1

8 19 3
1 2 0 1 1 1 2 0
3 1 4
3 2 2
1 4 1
7 4 10
5 4 7
4 2 5
5 6 4
4 7 3
8 5 10
3 6 8
8 1 10
5 2 10
6 7 3
4 3 9
6 2 5
4 8 10
3 8 3
1 7 8
1 3 9

Sample Output #1

11

Sample Input #2

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

Sample Output #2

Ushio!

Sample Input #3

6 13 3
2 2 2 1 0 2
1 4 4
3 4 8
5 3 2
4 5 6
2 3 2
1 3 3
1 2 4
3 1 4
6 3 6
3 2 6
2 1 6
4 2 9
5 2 1

Sample Output #3

7

Notes

$2 \le n \le 100$, $1 \le m \le n(n-1)$, $2 \le k \le 13$, $1 \le w_i \le 10^7$

The graph is guaranteed to have no duplicate edges or self-loops.

Sample Explanation

For Sample #1, the optimal solution is the path $3 \rightarrow 6 \rightarrow 7$.

For Sample #2, there is no solution.

For Sample #3, the optimal solution is the path $4 \rightarrow 5 \rightarrow 2$.

见题面 Input 部分

见题面 Output 部分