题号：NC214208
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
牛客大陆上有n个城市，这些城市和连接它们的m条道路形成了一个无向连通图。
牛牛王国是牛客大陆上最大的国家，首都在x城，某一天牛牛大陆上出现了许多魔物，牛牛国王希望能消灭这些魔物。
大魔法师告诉他在大陆的一个角落y城有一个神秘祭坛，只要集齐k种宝石并且到达祭坛就能消灭大陆上的所有魔物。
k种宝石散落在牛客大陆的城市里(每种宝石的数量可能不止一个,但每个城市里最多有一种宝石),并且由于宝石的力量，拥有同种宝石的城市之间可以直接传送而不消耗任何资源。
但是王国的所有道路都已经被魔物占据了，清空每条道路所需要的资源为
(道路清空一次以后就不用再次清空)，牛牛国王想要知道从王国首都x出发,拿到所有的k种宝石,并且到达祭坛y,需要消耗的最小资源。
牛牛王国是牛客大陆上最大的国家，首都在x城，某一天牛牛大陆上出现了许多魔物，牛牛国王希望能消灭这些魔物。
大魔法师告诉他在大陆的一个角落y城有一个神秘祭坛，只要集齐k种宝石并且到达祭坛就能消灭大陆上的所有魔物。
k种宝石散落在牛客大陆的城市里(每种宝石的数量可能不止一个,但每个城市里最多有一种宝石),并且由于宝石的力量，拥有同种宝石的城市之间可以直接传送而不消耗任何资源。
但是王国的所有道路都已经被魔物占据了，清空每条道路所需要的资源为
输入描述:
第一行五个整数n,m,k,x,y.
第二行n个整数,
,表示第i个城市拥有某种类的宝石,特别的0表示该城镇没有任何一种宝石.
后面的m行,每行三个整数u,v,w,表示城市u和v之间有一条道路,清空这个道路上的魔物需要消耗的资源为w.
保证首都x和祭坛y不拥有任何一种宝石.
输出描述:
输出仅一行,为从王国首都x出发,拿到所有的k种宝石,并且到达祭坛y,需要消耗的最小资源.(数据保证一定有解)
备注:
对于100%的数据：，
，
，
，
。
保证给出的无向图连通，但可能存在重边和自环。