上文说到moxin跟郭先生去看电影了，于是moxin又双叒破产了，无奈之下moxin只能又做起了卖菜的生意
当然卖菜就得进货，于是moxin就去进货了，这里的商店比较奇葩，遵守以下规则：
1.当两种不同的菜有着相同的价值的时候，那么可以进行交换(比如a种菜的价值等于b种菜的价值，那么a种菜可以与b种菜互相交换,互相交换是不需要花费额外的价值)
2.可以通过讨价还价，以一种菜的价值 + x价值RMB 来换取另一种菜
3.可以直接使用等于菜的价值RMB来购买一种菜
那么问题来了，moxin想要知道购买每一种菜最少需要花费多少RMB？
第一行输入T(1<=T<=10),代表有T组
第二行输入n,m（2<=n<=1e3, 0<=m<=1e3）
代表有n种菜，m种讨价还价的关系
接下来n行,每行有两个整数a,b(1<=a<=n, 1<=b<=1e5)
代表n种菜，第a种菜的价值为b
接下来m行，每行有三个整数a,b,c(1<=a<=n, 1<=b<=n, 1<=c<=1e5, a != b)
代表a种菜+价值为c的RMB可以换取b种菜
（数据一共7组）
n行
每行只有一个整数，每行的整数代表对应的第i种菜所需的最小花费
1 3 1 1 7 2 2 3 2 1 3 1
7 2 2