You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【问题描述】

小凯所在的城市的地铁网是一张n个点m条边的无向连通图，他要乘坐地铁从学校附近的 1号站点到达家附近的 n号站点。

地铁共有k条线路，每条边只属于一条地铁线路，但​相邻两个站点之间可能存在多条边​，因而相邻两个站点可能可以乘坐多条线到达。每条线路上的点​互相之间可以仅通过该线路到达​。

每条地铁线采用通票制度，票价为ci 元。即当小凯花 ci元买了 i号线的通票后，小凯乘坐 i号线不再需要付费。即便他离开 i 号线乘坐其它线路后再次乘坐i号线，他也不需要再次付费。

请你告诉小凯，他回家（到达n号站点）所需的最小花费是多少。

【输入格式】

第一行包含三个正整数 n,m,k，分别表示站点总数，边数，地铁线路数。

接下来一行k个正整数ci，表示每条线路的通票价格。

接下来m行每行三个正整数uj,vj,linej，分别表示第j条边连接的两个站点以及这条边从属的线路。

【输出格式】

输出仅一行一个正整数表示小凯回家所需的最小花费。

【输入输出样例】 【输入样例】

5 9 4
5 5 5 4 
2 5 1
4 1 2
2 4 3
1 2 3
1 3 4
3 1 2
2 3 1
4 1 4
4 5 1

【输出样例】 9

【样例1解释】

上图中每条边上标记的数字为其所属的地铁线。该组样例中小凯可以购买 1,4两条线的通票，总价为9 元，然后经过1-4-5车站回家。