暂无测试数据。

Description

为了响应国家加强中小学生体育锻炼的号召，\(\text{NOI2076}\) 决定以“跑路+做题”的形式考查 \(\text{OIers}\) 的计算机和体育综合能力。

\(\text{NOI2076}\) 的考场是一张有向图，其中包含了 \(n\) 个机房，编号 \(1\) 到 \(n\)，在 \(i\) 号机房内需要耗时 \(T_i\) 编写程序完成任务 \(i\)；还有 \(m\) 条通道连通了机房。第 \(i\) 条通道连接机房 \(u_i\) 和 \(v_i\)，耗时 \(w_i\) 通过该通道。开始的时候 \(\text{OIers}\) 都在 \(1\) 号机房，同时开始完成 \(1\) 号任务，后面往哪儿走、完成什么任务就看他们自己的抉择了，但是最后必须要完成所有 \(n\) 个任务。

\(\text{Scarral}\) 作为“关系户”，已经提前在所有电脑上安装了自动AC机，这些程序由 \(\text{Scarral}\) 来操控执行，为了让自己的测试成绩不那么假，他最多只能直接远程AC \(k\) 道题，耗时为 \(0\)。现在 \(\text{Scarral}\) 和大家一样从 \(1\) 号机房出发，他将选择至多 \(k\) 个机房不再经过（直接远程AC），也就是说他需要选择至少 \(n-k\) 个机房里的任务完成即可。

现在 \(\text{Scarral}\) 不太清楚到底应该选择哪 \(k\) 个机房不经过，请你帮他选择一下，求出完成 \(n-k\) 个任务的最小用时。

题意简述

有一个有向图，点数为 \(n\)，点编号 \(1\) 到 \(n\)，每个点有点权 \(T_i\)，边数为 \(m\)，第 \(i\) 条边连接 \(u_i\) 和 \(v_i\) 号结点，边长为 \(w_i\)。现给定 \(k(\leq n)\) 求从 \(1\) 到 \(n\) 选取任意 \(n-k\) 个结点经过（\(n-k\) 个结点包含 \(1\) 和 \(n\)）的最小经过点边权之和。

Input

第 \(1\) 行 \(3\) 个正整数 \(n\)、\(m\) 和 \(k\)。
第 \(2\) 行 \(n\) 个正整数表示 \(T_i\)。
第 \(3\) 行到第 \(m + 2\) 行每行 \(3\) 个正整数 \(u_i\)、\(v_i\) 和 \(w_i\)，表示第 \(i\) 条通道连接的机房和经过的耗时。

Output

如果能完成 \(n-k\) 个任务，输出总用时；如果不能完成，输出 -1。

Sample

Sample input

待填坑

Sample output

待填坑

Hint

数据保证

1. \(m\) 条通道均为弧即有向边，即可以从 \(u_i\) 到 \(v_i\)，而不能从 \(v_i\) 到 \(u_i\)；
2. 输入不包括自环和重边；
3. 不保证图连通。