小Biu看电影

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;

ll read() {
	ll ret = 0, flag = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		ret = (ret << 3) + (ret << 1) + (ch ^ '0');
		ch = getchar();
	}
	return ret * flag;
}

ll n, m, val[1000005], ans;
ll head[1000005], pre[1000005], to[1000005], dis[1000005], sz;
ll dist[1000005];
bool vis[100005];

void insert(ll u, ll v, ll w) {
	to[++sz] = v; dis[sz] = w; pre[sz] = head[u]; head[u] = sz;
}

void dijkstra(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));
			}
		}
	}
}

int main() {
	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]);
	return 0;
}