voiddijkstra(ll st){ priority_queue< pair<ll, ll> , vector< pair<ll, ll> > , greater< pair<ll, ll> > > q; q.push(make_pair(0, st)); while (!q.empty()) { ll x = q.top().second; q.pop(); if (vis[x]) continue; else vis[x] = 1; for (int i = head[x]; i; i = pre[i]) { ll y = to[i]; if (dist[y] > dist[x] + dis[i]) { dist[y] = dist[x] + dis[i]; q.push(make_pair(dist[y], y)); } } } }
intmain(){ n = read(); m = read(); for (int i = 1; i <= n; i++) { val[i] = read(); insert(0, i, val[i]); } for (int i = 1; i <= m; i++) { ll u, v, w; u = read(); v = read(); w = read(); insert(u, v, w * 2); insert(v, u, w * 2); } ans = 0x7fffffff; for (int j = 1; j <= n; j++) { dist[j] = 0x7fffffff; vis[j] = 0; } dist[0] = 0; dijkstra(0); for (int i = 1; i <= n; i++) printf("%lld\n", dist[i]); return0; }