#include <algorithm>
#include <assert.h>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MX 200005
#define oo 123123123123123123ll

using namespace std;

typedef long long ll;

template <typename T> void read(T& x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

struct EDGE
{
	int u, v; ll w;
	EDGE (const int& u0 = 0, const int& v0 = 0, const ll& w0 = 0) : u(u0), v(v0), w(w0) {}
	bool operator < (const EDGE& t) const {return w < t.w;}
};

struct VALUE
{
	ll mn[2], id[2], x[2];
	
	VALUE () {mn[0] = mn[1] = +oo, id[0] = id[1] = x[0] = x[1] = 0;}
	
	VALUE (int v0, int i0, int x0) {mn[0] = v0, mn[1] = +oo, id[0] = i0, id[1] = 0, x[0] = x0, x[1] = 0;}
	
	VALUE operator + (const VALUE& t) const
	{
		VALUE ret = *this;
		for(int i=0; i<2; i++)
		{
			if(t.mn[i] >= ret.mn[1]) continue;
			else if(t.mn[i] < ret.mn[1] && t.mn[i] >= ret.mn[0])
			{
				if(t.id[i] != ret.id[0]) ret.mn[1] = t.mn[i], ret.id[1] = t.id[i], ret.x[1] = t.x[i];
				else continue;
			}
			else
			{
				if(t.id[i] == ret.id[0]) ret.mn[0] = t.mn[i], ret.x[0] = t.x[i];
				else ret.mn[1] = ret.mn[0], ret.id[1] = ret.id[0], ret.x[1] = ret.x[0], ret.mn[0] = t.mn[i], ret.id[0] = t.id[i], ret.x[0] = t.x[i];
			}
		}
		return ret;
	}
	
	VALUE operator + (const ll& t) const
	{
		VALUE ret = *this;
		ret.mn[0] += t, ret.mn[1] += t;
		return ret;
	}
};

struct UNION
{
	int fa[MX];
	ll cost;
	
	int id(int x) {return (x==fa[x]) ? (x) : (fa[x]=id(fa[x]));}
	void merge(int x, int y, ll c)
	{
		if(id(x) != id(y))
		{
			fa[id(x)] = id(y);
			cost += c;
		}
	}
} U;

int fst[MX], lst[MX], val[MX], nxt[MX*2], pre[MX*2], v[MX*2], w[MX*2], lnum;

void addeg(int nu, int nv, int nw)
{
	lnum++;
	pre[fst[nu]] = lnum;
	nxt[lnum] = fst[nu];
	fst[nu] = lnum;
	if(!lst[nu]) lst[nu] = lnum;
	v[lnum] = nv;
	w[lnum] = nw;
}

VALUE dp[MX], fdp[MX];
int n, m;

void input()
{
	int a, b, c;
	read(n);
	for(int i=1; i<=n; i++) read(val[i]);
	for(int i=1; i<n; i++)
	{
		read(a); read(b); read(c);
		addeg(a, b, c);
		addeg(b, a, c);
	}
}

void dfs(int x, int f)
{
	dp[x] = VALUE();
	fdp[x] = VALUE();
	for(int i=fst[x]; i; i=nxt[i])
	{
		if(v[i] != f)
		{
			dfs(v[i], x);
			dp[x] = dp[x] + (dp[v[i]] + w[i]);
			dp[x] = dp[x] + VALUE(val[v[i]]+w[i], U.id(v[i]), v[i]);
		}
	}
}

void push(int x, int f)
{
	VALUE l, r;
	for(int i=fst[x]; i; i=nxt[i])
	{
		if(v[i] != f)
		{
			fdp[v[i]] = fdp[v[i]] + VALUE(val[x]+w[i], U.id(x), x);
			fdp[v[i]] = fdp[v[i]] + (fdp[x] + w[i]);
			fdp[v[i]] = fdp[v[i]] + (l + w[i]);
			l = l + (dp[v[i]] + w[i]);
			l = l + VALUE(val[v[i]]+w[i], U.id(v[i]), v[i]);
		}
	}
	for(int i=lst[x]; i; i=pre[i])
	{
		if(v[i] != f)
		{
			fdp[v[i]] = fdp[v[i]] + (r + w[i]);
			r = r + (dp[v[i]] + w[i]);
			r = r + VALUE(val[v[i]]+w[i], U.id(v[i]), v[i]);
		}
	}
	for(int i=fst[x]; i; i=nxt[i])
	{
		if(v[i] != f)
		{
			push(v[i], x);
		}
	}
}

EDGE avl[MX];
int top, ban[MX];
ll mnid[MX];

void work()
{
	for(int i=1; i<=n; i++) U.fa[i] = i;
	for(int i=1; i<=20; i++)
	{
		memset(mnid, 0x3f, sizeof(mnid));
		memset(ban, 0, sizeof(ban));
		dfs(1, 0);
		push(1, 0);
		top = 0;
		for(int x=1; x<=n; x++)
		{
			dp[x] = dp[x] + fdp[x];
			if(dp[x].x[0] && dp[x].id[0] != U.id(x))
			{
				avl[++top] = EDGE(dp[x].x[0], x, dp[x].mn[0] + val[x]);
				mnid[U.id(x)] = min(mnid[U.id(x)], dp[x].mn[0] + val[x]);
			}
			else if(dp[x].x[1] && dp[x].id[1] != U.id(x))
			{
				avl[++top] = EDGE(dp[x].x[1], x, dp[x].mn[1] + val[x]);
				mnid[U.id(x)] = min(mnid[U.id(x)], dp[x].mn[1] + val[x]);
			}
		}
		sort(avl+1, avl+top+1);
		for(int j=1; j<=top; j++)
			if(avl[j].w > mnid[U.id(avl[j].v)])
				ban[j] = 1;
		for(int j=1; j<=top; j++)
			if(!ban[j])
				U.merge(avl[j].u, avl[j].v, avl[j].w);
	}
	printf("%lld\n", U.cost);
}

int main()
{
	input();
	work();
	return 0;
}

Measured memory_bytes: 80768