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 ≤ n ≤ 3 ⋅ 10^5) — the number of cities.

The second line contains n integers w_1, w_2, …, w_n (0 ≤ w_{i} ≤ 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 ≤ u, v ≤ n, 1 ≤ c ≤ 10^9, u ≠ 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 → 1 → 3. 

<image>

The optimal way in the second example is 2 → 4. 

<image>
import java.io.*;
import java.util.*;

/**
 * Given a tree, find the maximal sum from one node to another where the value on the node is added and each edge
 * has a value that is subtracted. You can't have negtive sum on that path.
 *
 * We use DP to store at each node the value of the maximum sum from the node in one of its branches. In the same
 * dfs we check and try to add it to the maximal branch, this way the selected node is in the middle of the graph.
 */

public class The_Fair_Nut_the_Best_Path_1083A {
    static int n;
    static ArrayList<Pair> adjList[];
    static int[] gas;
    // maximum distance that I can reach from this node
    static long [] dp;
    static boolean[] visited;
    static long res = 0;

    static void dfs(int node, int p) {
        visited[node] = true;
        // minimal possible solution for node
        dp[node] = gas[node];
        for (Pair child : adjList[node]) {
            if (child.a == p) continue;
//            if (!visited[child.a]) {
                dfs(child.a, node);
                // getting the best result from all child branches and try to add it to another branch
                res = Math.max(res, dp[node] + dp[child.a] - child.b);
                // store in DP only the value of the max branch
                dp[node] = Math.max(dp[node], dp[child.a] - child.b + gas[node]);
//            }
        }
        //in case the a node has very big gas value
        res = Math.max(dp[node], res);
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        adjList = new ArrayList[n];
        dp = new long[n + 1];
        gas = new int[n];


        for (int i = 0; i < n; i++) {
            gas[i] = sc.nextInt();
            adjList[i] = new ArrayList<>();
        }

        for (int i = 1; i < n; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            int w = sc.nextInt();
            adjList[a].add(new Pair(b, w));
            adjList[b].add(new Pair(a, w));
        }

        visited = new boolean[n];
        dfs(0 ,-1);
        System.out.println(res);

    }

    static class Pair {
        int a;
        int b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream System) throws FileNotFoundException {
            br = new BufferedReader(new InputStreamReader(System));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

        public void waitForInput() {
            for (long i = 0; i < 3e9; i++)
                ;
        }
    }
}