P4962 朋也与光玉

> 一つ一つの光は小さくでも、たくさん集まればきっととても不思議な大きな力になるはず。 渚的离世、汐的离去...朋也的人生几乎陷入了一片黑暗。 但是，这会是结束吗？ 

光坂小镇是一个由 $n$ 个点（编号为 $1$ ~ $n$），$m$ 条有向边构成的图，每个节点上都有一个光玉，光玉共有 $k$ 种，编号为 $0$ ~ $k-1$。 为了使一切改变，朋也需要找齐全部的 $k$ 种光玉。他可以从任意一个节点出发，在图上任意行走，但不会经过同一个节点两次，每碰到一个光玉便会将其收集，收集到 $k$ 个光玉后，即经过了 $k$ 个节点后，便不会继续收集。请设计一种方案，使得朋也能够收集全部的 $k$ 种光玉，且走过的路径长度最短。 换句话说，每个点一个颜色，找到一条最短的点数为 $k$ 、恰好经过全部 $k$ 种颜色的路径。你需要求出这条路径的长度。

第一行，三个正整数 $n,\ m,\ k$，分别代表节点个数、边的条数、光玉的种类数。 第二行，共 $n$ 个正整数 $a_1$ ~ $a_n$，其中 $a_i$ 代表 $i$ 号节点的光玉种类编号。 接下来 $m$ 行，每行三个正整数 $u_i,\ v_i,\ w_i$，表示 $u_i$ 到 $v_i$ 有一条长度为 $w_i$ 的有向边。

输出一行，若有解则输出一个正整数表示满足条件的最短路径的长度，若无解则输出"Ushio!"（不含引号）

$2\le n\le 100$，$1\le m\le n(n-1)$，$2\le k\le 13$，$1\le w_i\le 10^7$ 保证图中没有重边、自环。 ## 样例解释 样例一，$3\rightarrow 6\rightarrow 7$ 为一组最优解。 样例二，无解。 样例三，最优解为 $4\rightarrow 5\rightarrow 2$。