U520550 LK的喀斯特地貌(travel)

``` 今年过年，我就不回家了，我准备到云南 喀斯特地貌，山清水秀 --LK ```

一年一度的春节到来，LK作为FY1Z的一名地理老师准备去云南，喀斯特地貌。 已知地表喀斯特地貌共有6种，分别简记为 A,B,C,D,E,F，LK想去看其中的**至少 $K$ 种**。 LK的旅游路线图可看作是一张**有向图**，每条有向边连接两个地点，LK从 $1$ 号点出发并最终回到 $1$ 号点。 现在告诉你这 $n$ 个旅游地点，其对应的地貌，以及每条有向边上路径的长度，请你为LK规划一条**最短的**旅游路线，满足其能看到至少 $K$ 种地貌。 注意， $1$ 号点**不属于任何地貌**。

第一行三个数 $n,m,K$ ，表示有向图的点数，边数，以及LK希望看到的地貌个数。 第二行 $n-1$ 个字母，第 $i$ 个字母 $c_i$ 表示第 $i+1$ 号点的的地貌。 之后的 $m$ 行每行三个数 $u,v,w$，表示一条有向边连接的两个点和路径长度

一个数，表示路径长度的最小值，若不存在，输出 $-1$

| 测试点编号 | $n\le$ | $m\le$ | $K\le$ | $w\le$ | $c_i\in$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |:-:| | $1\sim4$ | $6$ | $10$ | $6$ | $1$ |$\{A,B,C,D,E,F\}$| | $5\sim8$ | $100$ | $300$ | $6$ | $10000$ |$\{A,B,C,D,E,F\}$| | $9\sim10$ | $6000$ | $12000$ | $6$ | $10000$ |$\{A,B\}$| | $11\sim 12$ | $6000$ | $12000$ | $1$ | $10000$ |$\{A,B,C,D,E,F\}$| | $13\sim 20$ | $6000$ | $12000$ | $6$ | $10000$ |$\{A,B,C,D,E,F\}$|