题目描述

A市的地铁系统由$C$家公司运营，每家公司都开发了一些地铁线路，这些地铁线路连接了$n$个地铁站。 线路共有$m$条，每条双向边有三个属性$(u,v,c)$ 代表这条线路连接$(u,v)$两站，由$c$公司运营。 地铁系统的收费规则为：每家公司都有单独的地铁票，售价为$p[i]$，一张票允许你 "不间断" 地任意乘坐这家公司的地铁线路，直到你到达终点或者换乘其他公司的线路。 也就是说：对于路径上相邻的边$(u,v,c1)$和$(u,v,c2)$：若$c_1 =c _2$则不花钱，否则需要花费$p[c_2]$重 新买票，当然从起点上车时也要买票。 现在给定$n$和$m$条边，以及$p$数组，请你计算从起点$1$到所有点所需的最小花费。

输入格式

第一行3个整数 $n,m,c$ 第二行 $c$个正整数$p[i]$ 接下来$m$行，每行3个正整数$(u,v,c)$代表一条双向边，保证$u,v$之间只有1条线路，保证$u \neq v$

输出格式

输出一行$n$个整数，代表从起点$1$出发到$i=1...n$的最小花费，特别地若不存在路径输出 -1。

样例

3 3 2
1 2
1 2 1
2 3 1
3 1 2

0 1 1

8 11 5
10 5 1 20 2
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

0 10 6 5 10 6 6 8

3 1 2
2 3
1 2 1

0 2 -1

样例 4-5

见下发样例

样例2解释 1到2的最优路线：1->3->2 1到3的最优路线：1->4->3 1到4的最优路线：1->4 1到5的最优路线：1->3->2->5 1到6的最优路线：1->4->3->6 1到7的最优路线：1->4->3->7 1到8的最优路线：1->4->3->7->8

数据范围

对于20%的数据：$n,m,c \leq 5$ 对于40%的数据：$n,m,c \leq 100$ 对于60%的数据：$n \leq 10^{5},m \leq 2*10^{5},c \leq 100$ 对于100%的数据：$1 \leq n \leq 10^{5}$,$0 \leq m \leq 2*10^{5}$,$1 \leq c \leq 10^{6}$,$0 \leq p[i] \leq 10^{5}$,$1 \leq c \leq C$