PIPI对收藏宝石特别感兴趣，他特意学习了两种魔法来获得他想要的宝石。
第一种魔法是，对于PIPI想要收藏的n种宝石，他可以用ai的魔力来创造一个第i种宝石。
第二种魔法是，对于某种宝石，PIPI可以使用两种宝石来合成那一种宝石。此魔法无需消耗魔力。
请问PIPI创造每种宝石所需的最小魔力是多少？

第一行两个正整数n,m，其中有：n<=10^5,m<=10^5。
第二行n个正整数，第i个数为ai，表示可以用ai的魔力创造一个第i种宝石，ai<=10^9。
接下来m行，每行三个正整数a,b,c，表示一个第a种宝石和一个第b种宝石，可以合成一个第c种宝石，a,b,c<=n。

输出i行，第i行的数字表示创造一个第i种宝石所需的最小魔力。

样例解释：
使用1魔力可以创造出一个第1种宝石。
使用1魔力可以创造出一个第2种宝石。
使用2魔力可以创造出一个第1种宝石和一个第2种宝石，再把它们合成一个第3种宝石。