#1913. 交换礼物

交换礼物

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

学校举行跳蚤市场,有交换礼物的环节。礼物从1\red{1}N\red{N}编号。小夏想要得到编号为1\red{1}的礼物。 获取礼 物

有两种方式:

1,\red{1,}您可以直接购买礼物,第 i\red{i }个礼物花费ci\red{c_i}钱。

2,\red{2,}您可以选择交换礼物,该活动支持M\red{M}种交换方式:两个特定的不同礼物,可以换取一个指定礼 物。

帮助小夏花最少的钱获得第1\red{1}号礼物。

输入格式

第一行一个数T\red{T,}表示 T\red{T}组数据。

每组数据第一行两个数: N\red{N}M\red{M }

接下来一行N\red{N}个数,表示 N\red{N}件物品的价格;

接下来 M\red{M,}每行三个数,Ti,Ui\red{T_i,U_i}Vi\red{V_i ,}表示可以使用礼物 Ui\red{U_i}Vi\red{V_i }交换得到Ti\red{T_i }

输出格式

每组数据输出一个数,表示获得礼物1\red{1}的最小费用。

样例

输入样例

2
5 3
5 0 1 2 5
5 2 3
4 2 3
1 4 5
3 1
2 2 1
1 2 3

输出样例

2
2

提示

对于30%\red{30\%}的数据,M=N1\red{M=N-1 ,}礼物之间恰好形成一棵树的形式;

对于 40%\red{40\%}的数据,保证礼物之间的依赖关系,不会形成环;

对于100%\red{100\% }的数据, N<=20000\red{N<=20000,}M<=100000\red{M<=100000 ,}T<=10\red{T<=10 }

小云雀c++高中组重现

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2022-5-3 18:00
结束于
2022-5-5 18:00
持续时间
48 小时
主持人
参赛人数
27