The Fair Nut is going to travel to the Tree Country, in which there are $n$ cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city $u$ and go by a simple path to city $v$. He hasn't determined the path, so it's time to do it. Note that chosen path can consist of only one vertex.

A filling station is located in every city. Because of strange law, Nut can buy only $w_i$ liters of gasoline in the $i$-th city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can't choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.

He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$) — the number of cities.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \leq w_{i} \leq 10^9$) — the maximum amounts of liters of gasoline that Nut can buy in cities.

Each of the next $n - 1$ lines describes road and contains three integers $u$, $v$, $c$ ($1 \leq u, v \leq n$, $1 \leq c \leq 10^9$, $u \ne v$), where $u$ and $v$ — cities that are connected by this road and $c$ — its length.

It is guaranteed that graph of road connectivity is a tree.


-----Output-----

Print one number — the maximum amount of gasoline that he can have at the end of the path.


-----Examples-----
Input
3
1 3 3
1 2 2
1 3 2

Output
3

Input
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1

Output
7



-----Note-----

The optimal way in the first example is $2 \to 1 \to 3$.  [Image] 

The optimal way in the second example is $2 \to 4$.  [Image]

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
from sys import stdin, setrecursionlimit
import threading
n = int(stdin.readline())
w = [int(x) for x in stdin.readline().split()]
graph = [{} for x in range(n)]
for road in range(n - 1):
	(u, v, c) = [int(x) for x in stdin.readline().split()]
	u -= 1
	v -= 1
	if v in graph[u]:
		graph[u][v] = min(graph[u][v], c)
	else:
		graph[u][v] = c
	if u in graph[v]:
		graph[v][u] = min(graph[v][u], c)
	else:
		graph[v][u] = c
gas = [{} for x in range(n)]
highs = [[0, 0] for x in range(n)]
path = [(0, 0)]
ind = 0
while ind < len(path):
	(cur, par) = path[ind]
	edges = graph[cur]
	for x in edges:
		if x != par:
			path.append((x, cur))
	ind += 1

def mostGas(node, parent):
	edges = graph[node]
	high = w[node]
	high2 = w[node]
	for x in edges:
		if x != parent:
			gas[node][x] = highs[x][0] + w[node] - edges[x]
			if gas[node][x] > high:
				(high, high2) = (gas[node][x], high)
			elif gas[node][x] > high2:
				high2 = gas[node][x]
	highs[node] = [high, high2]
	return high
for (x, y) in path[::-1]:
	mostGas(x, y)
high = 0
for x in range(n):
	high = max(high, highs[x][0] + highs[x][1] - w[x])
print(high)


import sys
readline = sys.stdin.readline
from collections import Counter

def getpar(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[0] = -1
	par[p] - 1
	stack = [p]
	visited = set([p])
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			stack.append(vf)
	return par

def topological_sort_tree(E, r):
	Q = [r]
	L = []
	visited = set([r])
	while Q:
		vn = Q.pop()
		L.append(vn)
		for vf in E[vn]:
			if vf not in visited:
				visited.add(vf)
				Q.append(vf)
	return L

def getcld(p):
	res = [[] for _ in range(len(p))]
	for (i, v) in enumerate(p[1:], 1):
		res[v].append(i)
	return res
N = int(readline())
We = list(map(int, readline().split()))
Edge = [[] for _ in range(N)]
Cost = Counter()
geta = N + 1
for _ in range(N - 1):
	(a, b, c) = list(map(int, readline().split()))
	a -= 1
	b -= 1
	Edge[a].append(b)
	Edge[b].append(a)
	Cost[b * geta + a] = c
	Cost[a * geta + b] = c
P = getpar(Edge, 0)
L = topological_sort_tree(Edge, 0)
C = getcld(P)
dp = [0] * N
candi = [[0, 0] for _ in range(N)]
ans = 0
for l in L[::-1][:-1]:
	dp[l] += We[l]
	p = P[l]
	k = dp[l] - Cost[l * geta + p]
	if k > 0:
		dp[p] = max(dp[p], k)
		candi[p].append(k)
	res = max(candi[l])
	candi[l].remove(res)
	ans = max(ans, We[l] + res + max(candi[l]))
res = max(candi[0])
candi[0].remove(res)
ans = max(ans, We[0] + res + max(candi[0]))
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
adj = [[] for i in range(n)]
for i in range(n - 1):
	(u, v, w) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append((v, w))
	adj[v].append((u, w))
best = [0] * n
ans = 0

def dfs(u):
	stack = list()
	visit = [False] * n
	stack.append((u, -1))
	while stack:
		(u, par) = stack[-1]
		if not visit[u]:
			visit[u] = True
			for (v, w) in adj[u]:
				if v != par:
					stack.append((v, u))
		else:
			cand = []
			for (v, w) in adj[u]:
				if v != par:
					cand.append(best[v] + a[v] - w)
			cand.sort(reverse=True)
			cur = a[u]
			for i in range(2):
				if i < len(cand) and cand[i] > 0:
					cur += cand[i]
			global ans
			ans = max(ans, cur)
			best[u] = cand[0] if len(cand) > 0 and cand[0] > 0 else 0
			stack.pop()
dfs(0)
print(ans)