Description

Hikarizaka Town is a directed graph with $n$ nodes (numbered $1$ to $n$) and $m$ directed edges. Each node has a light orb. There are $k$ types of light orbs, numbered $0$ to $k-1$.

To change everything, Tomoya needs to collect all $k$ types of light orbs. He may start from any node and walk freely in 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, that is, after visiting $k$ nodes, he will stop collecting. Design a plan so that Tomoya can collect all $k$ types of light orbs, and the total path length is as short as possible.

In other words, each node has one color. Find a shortest path that visits exactly $k$ nodes and covers all $k$ colors exactly once. You need to output the length of this path.

Input Format

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

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

The next $m$ lines each contain three positive integers $u_i,\ v_i,\ w_i$, indicating a directed edge from $u_i$ to $v_i$ with length $w_i$.

Output Format

Output one line. If a solution exists, output a positive integer representing the length of the shortest path that satisfies the condition. If no solution exists, output Ushio! (without quotes).

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

11

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

Ushio!

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

7

Hint

Constraints: $2\le n\le 100$，$1\le m\le n(n-1)$，$2\le k\le 13$，$1\le w_i\le 10^7$.

It is guaranteed that the graph has no multiple edges or self-loops.

Translated by ChatGPT 5