U114690 赛艇比赛

小明去某个地区观看赛艇比赛。

小明去某个地区观看赛艇比赛，这个地区共有n个城市和m条道路，每个城市都有赛艇比赛，在第i个 城市观看赛艇表演的价钱为ai， 去其他城市观看也需要支付赛艇表演的价格。任意两个城市之间通过 一条公路连接，并且道路是双向通行的， 观看赛艇比赛时经过的每一条道路都要支付一定的过路费， 观看完比赛返回家时经过的每一条道路也要支付过路费。 对于每个城市u，你需要为小明确定一个城市v，使得从u出发，前往v看赛艇表演，再从v回到u，u可 以等于v，要求花费的总金额尽量的少。请根据题目给出的数据输出总金额。

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

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

对于前30%的数据，n