Problem: DZY loves planting, and he enjoys solving tree problems.

DZY has a weighted tree (connected undirected graph without cycles) containing n nodes (they are numbered from 1 to n). He defines the function g(x, y) (1 ≤ x, y ≤ n) as the longest edge in the shortest path between nodes x and y. Specially g(z, z) = 0 for every z.

For every integer sequence p1, p2, ..., pn (1 ≤ pi ≤ n), DZY defines f(p) as <image>. 

DZY wants to find such a sequence p that f(p) has maximum possible value. But there is one more restriction: the element j can appear in p at most xj times.

Please, find the maximum possible f(p) under the described restrictions.

Input

The first line contains an integer n (1 ≤ n ≤ 3000).

Each of the next n - 1 lines contains three integers ai, bi, ci (1 ≤ ai, bi ≤ n; 1 ≤ ci ≤ 10000), denoting an edge between ai and bi with length ci. It is guaranteed that these edges form a tree.

Each of the next n lines describes an element of sequence x. The j-th line contains an integer xj (1 ≤ xj ≤ n).

Output

Print a single integer representing the answer.

Examples

Input

4
1 2 1
2 3 2
3 4 3
1
1
1
1


Output

2


Input

4
1 2 1
2 3 2
3 4 3
4
4
4
4


Output

3

Note

In the first sample, one of the optimal p is [4, 3, 2, 1].

Solution (in JAVA):

Solution:
import javafx.util.*;

import java.io.*;
import java.util.*;
import java.util.zip.CheckedOutputStream;

import static java.lang.Math.*;
import static java.util.Arrays.*;


public class Main{

    void run(){
        Locale.setDefault(Locale.US);
        boolean my;
        try {
            my = System.getProperty("MY_LOCAL") != null;
        } catch (Exception e) {
            my = false;
        }
        try{
            err = System.err;
            if( my ){
                sc  = new FastScanner(new BufferedReader(new FileReader("input.txt")));
//                sc  = new FastScanner(new BufferedReader(new FileReader("C:\\myTest.txt")));
                out = new PrintWriter   (new FileWriter("output.txt"));
            }
            else {
                sc  = new FastScanner( new BufferedReader(new InputStreamReader(System.in)) );
                out = new PrintWriter( new OutputStreamWriter(System.out));
            }
//            out = new PrintWriter(new OutputStreamWriter(System.out));
        }catch(Exception e){
            MLE();
        }
        if( my )
            tBeg = System.currentTimeMillis();
        solve();
        if( my )
            err.println( "TIME: " + (System.currentTimeMillis() - tBeg ) / 1e3 );
        exit(0);
    }

    void exit( int val ){
        err.flush();
        out.flush();
        System.exit(val);
    }

    double tBeg;
    FastScanner sc;
    PrintWriter out;
    PrintStream err;

    class FastScanner{

        StringTokenizer st;
        BufferedReader br;

        FastScanner( BufferedReader _br ){
            br = _br;
        }

        String readLine(){
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        String next(){
            while( st==null || !st.hasMoreElements() )
                st = new StringTokenizer(readLine());
            return st.nextToken();
        }

        int nextInt(){ return Integer.parseInt(next()); }
        long nextLong(){ return Long.parseLong(next()); }
        double nextDouble(){ return Double.parseDouble(next()); }
    }

    void MLE(){
        int[][] arr = new int[1024*1024][]; for( int i = 0; i < 1024*1024; ++i ) arr[i] = new int[1024*1024];
    }

    void MLE( boolean doNotMLE ){ if( !doNotMLE ) MLE(); }

    void TLE(){
        for(;;);
    }

    public static void main(String[] args) {
        new Main().run();
//        new Thread( null, new Runnable() {
//            @Override
//            public void run() {
//                new Main().run();
//            }
//        }, "Lolka", 256_000_000L ).run();
    }

    ////////////////////////////////////////////////////////////////

    class DSU{
        int n;
        int[] pr, cnt;
        int[] sum;

        public DSU(int _n) {
            n = _n;
            pr = new int[n];
            for (int i = 0; i < n; i++) {
                pr[i] = i;
            }
            cnt = new int[n];
            fill( cnt, 1 );
            sum = new int[n];
        }

        public int getParent(int v) {
            if( pr[v] == v ) return v;
            return pr[v] = getParent(pr[v]);
        }

        public boolean unit(int a, int b, int SUM) {
//            err.printf( "%d %d\n", a, b );
            a = getParent(a);
            b = getParent(b);
            if( a == b ) MLE();
            if( cnt[a] < cnt[b] ){
                int t = a;
                a = b;
                b = t;
            }
            sum[a] += sum[b];
            cnt[a] += cnt[b];
            pr[b] = a;

            return cnt[a] <= SUM - sum[a];
        }
    }

    void solve(){
        int n;
        TreeMap<Integer,ArrayList<Pair<Integer,Integer>>> tm;
        DSU dsu;
        int sum;

        n = sc.nextInt();
        tm = new TreeMap<>();
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            if( !tm.containsKey(c) )
                tm.put( c, new ArrayList<>() );
            tm.get(c).add( new Pair<>(a,b) );
        }

        sum = 0;
        dsu = new DSU(n+1);
        for (int i = 1; i <= n; i++) {
            sum += dsu.sum[i] = sc.nextInt();
        }

        int ans = 0;
        cyc:
        for (int w : tm.keySet()) {
            ans = w;
            for (Pair<Integer, Integer> rib : tm.get(w)) {
                if( !dsu.unit( rib.getKey(), rib.getValue(), sum ) ){
                    break cyc;
                }
            }
        }
        out.println( ans );
    }

}