<题目链接>
题目大意：
有n座城市，每一个城市都有一个听演唱会的价格，这n座城市由m条无向边连接，每天变都有其对应的边权。现在要求出每个城市的人，看一场演唱会的最小价值(总共花费的价值=所看演唱会的价值+该城市的人去那个城市看演唱会的往返距离之和)。
解题分析：
比较好的一道最短路题，主要考察建图能力。我们不妨建立一个虚拟源点，然后该源点向所有的边都连上一条无向边，边权为对应点的点权。然后所有的点之间通过m条边连接，只不过边权设为2倍原边权。最后就是从源点跑一遍最短路，就能得到每个城市的人能够看演唱会的最小价值。这里有点逆向思维的意思，源点向所有点连一条边权为$a[i]$的边，代表该点作为最后看演唱会的城市，所贡献的价值。
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int N = 2e5+ ;
const ll INF = 1e18; template<typename T>
inline void read(T&x){
x=;int f=;char c=getchar();
while(c<'' || c>''){ if(c=='-')f=-;c=getchar(); }
while(c>='' && c<=''){ x=x*+c-'';c=getchar(); }
x*=f;
} struct Edge{ int from,to,nxt;ll val; }e[N<<];
int n,m,cnt;
int head[N],vis[N]; struct Node{
int loc;ll dist;
bool operator < (const Node &tmp)const{ return dist>tmp.dist; }
}node[N]; inline void add(int u,int v,ll w){
e[++cnt]=(Edge){u,v,head[u],w};
head[u]=cnt;
}
inline void Dij(int st){
for(int i=;i<=n;i++){
vis[i]=,node[i]=(Node){i,INF};
}
priority_queue<Node>q;
node[].dist=;
q.push(node[]);
while(q.size()){
int u=q.top().loc;q.pop();
if(vis[u])continue;
vis[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;ll cost=e[i].val;
if(node[v].dist>node[u].dist+cost){
node[v].dist=node[u].dist+cost;
q.push(node[v]);
}
}
}
}
int main(){
read(n);read(m);
for(int i=;i<=m;i++){
int u,v;ll w;
read(u);read(v);read(w);
add(u,v,*w);add(v,u,*w);
}
for(int i=;i<=n;i++){
ll val;read(val);
add(,i,val);add(i,,val);
}
Dij();
for(int i=;i<=n;i++)
i==n?printf("%lld\n",node[i].dist):printf("%lld ",node[i].dist);
}