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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author @Ziklon
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    ATheFairNutAndTheBestPath solver = new ATheFairNutAndTheBestPath();
    solver.solve(1, in, out);
    out.close();
  }

  static class ATheFairNutAndTheBestPath {
    List<int[]>[] adj;
    int[] W;
    long[] dp;
    long ans = 0;

    public void solve(int testNumber, InputReader in, OutputWriter out) {
      int n = in.readInt();
      W = in.readIntArray(n);

      adj = new List[n];
      dp = new long[n];
      for (int i = 0; i < n; ++i) adj[i] = new ArrayList<>();

      for (int i = 1; i < n; ++i) {
        int u = in.readInt() - 1, v = in.readInt() - 1, c = in.readInt();
        adj[u].add(new int[] {v, c});
        adj[v].add(new int[] {u, c});
      }

      dfs(0, -1);
      out.printLine(ans);
    }

    private void dfs(int root, int parent) {

      dp[root] = W[root];
      long big1 = 0, big2 = 0;

      for (int[] child : adj[root])
        if (child[0] != parent) {
          dfs(child[0], root);
          dp[root] = Math.max(dp[root], dp[child[0]] - child[1] + W[root]);
          if (dp[child[0]] - child[1] > big2) {
            big2 = dp[child[0]] - child[1];
            if (big2 > big1) {
              long tmp = big1;
              big1 = big2;
              big2 = tmp;
            }
          }
        }
      ans = Math.max(ans, dp[root]);
      ans = Math.max(ans, big1 + big2 + W[root]);
    }
  }

  static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private InputReader.SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int[] readIntArray(int size) {
      int[] array = new int[size];
      for (int i = 0; i < size; i++) {
        array[i] = readInt();
      }
      return array;
    }

    public int read() {
      if (numChars == -1) {
        throw new InputMismatchException();
      }
      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (numChars <= 0) {
          return -1;
        }
      }
      return buf[curChar++];
    }

    public int readInt() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);
    }
  }

  static class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
      writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void close() {
      writer.close();
    }

    public void printLine(long i) {
      writer.println(i);
    }
  }
}
