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

题目描述

又到了8月17日，一年一度的赛艇大会开始了！
不过ljt12138却因此感到头疼，因为有很多朋友都来问他“我从家出发观看赛艇表演至少要花多少钱？”这样的问题。
ljt12138身为一名优秀的集训队员，解决这样的问题对他来说当然是小菜一碟，不过他打算用这道题来考考你。
具体来说，一共有n个城市和m条道路，在第i个城市观看赛艇表演的价钱为ai。当然也可以选择到其他城市观看。每条道路连接着两个城市，且是双向通行的，并且经过一条道路要支付一定的过路费。当然，看完表演还要回家，因此往返都会产生过路费。
因为前来膜拜ljt12138的人很多，所以你对每个城市作为起点的情况都要算一遍。
形式化地讲，对于每个城市u，你需要为她确定一个城市v，使得从u出发，前往v看赛艇表演，再从v回到u，花费的总金额尽量的少。你只需要输出这个总金额就可以了。

输入格式

第一行两个正整数n和m。
接下来m行，每行三个正整数u，v，w，表示有一条双向道路连接u和v，且每经过一次的过路费是w。
接下来一行n个数，第i个数表示在第i个城市观看赛艇表演的价钱。

输出格式

输出一行n个数，第i个数表示从第i个城市出发至少要花多少钱。

数据范围

本题有20个测试点。

• 对于前30%的数据，n<=10，m<=20。
• 对于前50%的数据，n<=100，m<=500。
• 对于前70%的数据，n<=1500，m<=2000。
• 对于前85%的数据，图的结构以某种方式随机生成。
• 对于100%的数据，n<=2e5，m<=2e5，过路费和门票钱都在[1,1e12]内。