P4962 Tomoya and the Light Orbs

> Even if each light is small, if many gather together, it will surely become a very mysterious and great power. Nagisa’s death, Ushio’s departure... Tomoya’s life has almost fallen into complete darkness. But is this the end? 

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.

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 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).

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