题目背景

一つ一つの光は小さくでも、たくさん集まればきっととても不思議な大きな力になるはず。

渚的离世、汐的离去...朋也的人生几乎陷入了一片黑暗。

但是，这会是结束吗？

题目描述

光坂小镇是一个由 $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!"（不含引号）

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

提示

$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$。