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.math.BigInteger;
import java.security.SecureRandom;
import java.text.DecimalFormat;
import java.util.*;
import java.io.*;




public class Main {
    private static int n;
    private static int [] fr,to,W;
    private static ArrayList<Integer> [] E;
    private static long [] val,suff;
    private static int [] gas;

    private static long dfs(int u,int p) {
        long ret = 0;
        for (int i = 0;i < E[u].size();i++) {
            int e = E[u].get(i);
            int v = fr[e] + to[e] - u;
            long tmp = 0;
            if (v != p) tmp = dfs(v,u) - W[e];
            ret = Math.max(ret,tmp);
        }
        return val[u] = ret + gas[u];
    }
    private static long dfs(int u,int p,long fp) {
        fp = Math.max(fp,0L);
        long mx = 0,sp = 0;
        for (int i = E[u].size()-1;i >= 0;i--) {
            int e = E[u].get(i);
            int v = fr[e] + to[e] - u;
            long tmp = val[v] - W[e];
            if (v == p) tmp = fp;
            if (v != p) suff[v] = mx;
            else sp = mx;
            mx = Math.max(mx,tmp);
        }

        long ret = fp + gas[u];
        mx = 0;
        for (int i = 0;i < E[u].size();i++) {
            int e = E[u].get(i);
            int v = fr[e] + to[e] - u;

            long suf = suff[v];
            if (v == p) suf = sp;

            long bestSibling = Math.max(mx, suf);
            if (v != p) {
                ret = Math.max(ret, dfs(v, u,  bestSibling + gas[u] - W[e]));
            }

            long tmp = val[v] - W[e];
            if (v == p) tmp = fp;
            mx = Math.max(mx,tmp);
        }
        return ret;
    }


    public static void main(String[] args) throws Exception {
        IO io ;
        try {
            io = new IO("in.in", null);
        } catch (IOException e) {
            io = new IO(null, null);
        }
        n = io.getNextInt();
        fr = new int[n-1];
        to = new int[n-1];
        W = new int[n-1];
        E = new ArrayList[n+1];
        val = new long[n+1];
        gas = new int[n+1];
        for (int u = 1;u <= n;u++) {
            E[u] = new ArrayList<>();
            gas[u] = io.getNextInt();
        }
        for (int e = 0;e < n-1;e++) {
            fr[e] = io.getNextInt();
            to[e] = io.getNextInt();
            W[e] = io.getNextInt();
            E[fr[e]].add(e);
            E[to[e]].add(e);
        }
        suff = new long[n+1];
        dfs(1,0);
        io.println(dfs(1,0,0));
        io.close();
    }
    private static final int onebillion7 = 1000000007;
}


class MCMF{
    public static long oo = 1L << 60,inf = oo/300;
    private int n,src,snk;
    public ArrayList<Integer> fr,to;
    public ArrayList<Integer> cap;
    private ArrayList<Long> cost;
    private ArrayList<Boolean> isInner;
    private long [] dist;
    private int [] iE;

    public MCMF(int n,int src,int snk) {
        this.n = n;
        this.src = src;
        this.snk = snk;
        dist = new long[n];
        iE = new int[n];
        fr = new ArrayList<>();
        to = new ArrayList<>();
        cap = new ArrayList<>();
        cost = new ArrayList<>();
        isInner = new ArrayList<>();
    }

    private int addEdge(int a,int b,int w,long c,boolean inner) {
        int e = fr.size();
        fr.add(a);
        to.add(b);
        cap.add(w);
        cost.add(c);
        isInner.add(inner);
        return e;
    }
    public int addEdge(int a,int b,int w1,int w2,long c,boolean inner) {
        int e = addEdge(a,b,w1,c,inner);
        addEdge(b,a,w2,-c,inner);
        return e;
    }



    private static boolean [] vis;
    private boolean exists(){
        if (vis == null) vis = new boolean[n];
        for (int i = 0;i < vis.length;i++) vis[i] = false;
        if (dist[snk] >= oo) return false;
        int u = snk;
        while (u != src) {
            if (vis[u]) return false;
            vis[u] = true;
            if (iE[u] == -1) return false;
            u = fr.get(iE[u]);
        }
        return true;
    }
    private boolean bellman(){
        for (int i = 0;i < n;i++) {
            dist[i] = oo;
            iE[i] = -1;
        }
        dist[src] = 0;
        for (int i = 0;i < n-1;i++)
            for (int e = 0;e < fr.size();e++) {
                int a = fr.get(e),b = to.get(e);
                int ca = cap.get(e);
                long co = cost.get(e);
                if (ca == 0) continue;
                if (dist[a] + co < dist[b]) {
                    dist[b] = dist[a] + co;
                    iE[b] = e;
                }
            }
        return exists();
    }

    private pair augment(){
        ArrayList<Integer> path = new ArrayList<>();
        int u = snk;
        int f = Integer.MAX_VALUE;
        long c = 0;
        while (u != src) {
            path.add(u);
            int e = iE[u];
            f = Math.min(f,cap.get(e));
            if (!isInner.get(e))
                c += cost.get(e);
            u = fr.get(e);
        }
        path.add(src);
        Collections.reverse(path);

        u = snk;
        int ctr = 0;
        while (u != src) {
            int e = iE[u];
            ctr += isInner.get(e) ? 1 : 0;
            cap.set(e,cap.get(e) - f);
            cap.set(e^1,cap.get(e^1) + f);
            u = fr.get(e);
        }
        return new pair(f,c*f);
    }

    public pair mcmf(){
        long cost = 0;
        int flow = 0;
        while (bellman())  {
            pair res = augment();
            cost += res.cost;
            flow += res.flow;
        }
        return new pair(flow,cost);
    }
}

class pair{
    int flow;
    long cost;
    public pair(int f,long c) {
        flow = f;
        cost = c;
    }
}

class Buffer{
    ArrayList<Character> AS;
    public Buffer(){
        AS = new ArrayList<>();
    }
    public void append(String s){
        for (char c : s.toCharArray())
            AS.add(c);
    }
    public void appendLine(String s) {
        append(s);
        AS.add('\n');
    }
    public void clear(){
        AS.clear();
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        for (char c : AS)
            sb.append(c);
        return sb.toString();
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

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

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}



class PollardRho {
    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();
    private static ArrayList<Long> primes = new ArrayList<>();

    private static BigInteger rho(BigInteger N) {
        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        // check divisibility by 2
        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    private static void factor(BigInteger N) {
        if (N.compareTo(ONE) == 0) return;
        if (N.isProbablePrime(20)) {
            primes.add(N.longValue());
            return;
        }
        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }


    public static ArrayList<Long> factor(Long n) {
        primes.clear();
        factor(BigInteger.valueOf(n));
        return primes;
    }
}
