Problem: There are n cities in the country of Berland. Some of them are connected by bidirectional roads in such a way that there exists exactly one path, which visits each road no more than once, between every pair of cities. Each road has its own length. Cities are numbered from 1 to n.

The travelling time between some cities v and u is the total length of the roads on the shortest path from v to u. 

The two most important cities in Berland are cities 1 and n.

The Berland Ministry of Transport decided to build a single new road to decrease the traffic between the most important cities. However, lots of people are used to the current travelling time between the most important cities, so the new road shouldn't change it too much. 

The new road can only be built between such cities v and u that v ≠ u and v and u aren't already connected by some road.

They came up with m possible projects. Each project is just the length x of the new road.

Polycarp works as a head analyst at the Berland Ministry of Transport and it's his job to deal with all those m projects. For the i-th project he is required to choose some cities v and u to build the new road of length x_i between such that the travelling time between the most important cities is maximal possible. 

Unfortunately, Polycarp is not a programmer and no analyst in the world is capable to process all projects using only pen and paper. 

Thus, he asks you to help him to calculate the maximal possible travelling time between the most important cities for each project. Note that the choice of v and u can differ for different projects.

Input

The first line contains two integers n and m (3 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ m ≤ 3 ⋅ 10^5) — the number of cities and the number of projects, respectively.

Each of the next n - 1 lines contains three integers v_i, u_i and w_i (1 ≤ v_i, u_i ≤ n, 1 ≤ w_i ≤ 10^9) — the description of the i-th road. It is guaranteed that there exists exactly one path, which visits each road no more than once, between every pair of cities.

Each of the next m lines contains a single integer x_j (1 ≤ x_j ≤ 10^9) — the length of the road for the j-th project.

Output

Print m lines, the j-th line should contain a single integer — the maximal possible travelling time between the most important cities for the j-th project.

Example

Input

7 2
1 2 18
2 3 22
3 4 24
4 7 24
2 6 4
3 5 12
1
100


Output

83
88

Note

The road network from the first example:

<image>

You can build the road with length 1 between cities 5 and 6 to get 83 as the travelling time between 1 and 7 (1 → 2 → 6 → 5 → 3 → 4 → 7 = 18 + 4 + 1 + 12 + 24 + 24 = 83). Other possible pairs of cities will give answers less or equal to 83.

Solution (in JAVA):

Solution:


import java.io.*;
import java.nio.charset.Charset;
import java.util.*;

public class CF1016F {
    public static void main(String[] args) throws Exception {
        boolean local = System.getProperty("ONLINE_JUDGE") == null;
        boolean async = false;

        Charset charset = Charset.forName("ascii");

        FastIO io = local ? new FastIO(new FileInputStream("/Users/daltao/DATABASE/TESTCASE/CF1016F.in"), System.out, charset) : new FastIO(System.in, System.out, charset);
        Task task = new Task(io);

        if (async) {
            Thread t = new Thread(null, task, "dalt", 1 << 27);
            t.setPriority(Thread.MAX_PRIORITY);
            t.start();
            t.join();
        } else {
            task.run();
        }

        if (local) {
            io.cache.append("\n\n--memory -- " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()));
        }

        io.flush();
    }

    public static class Task implements Runnable {
        final FastIO io;

        public Task(FastIO io) {
            this.io = io;
        }

        @Override
        public void run() {
            solve();
        }

        public void solve() {
            int n = io.readInt();
            int m = io.readInt();

            Node[] nodes = new Node[n + 1];
            for (int i = 0; i <= n; i++) {
                nodes[i] = new Node();
                nodes[i].id = i;
            }

            for (int i = 1; i < n; i++) {
                Node a = nodes[io.readInt()];
                Node b = nodes[io.readInt()];

                Edge edge = new Edge();
                edge.src = a;
                edge.dst = b;
                edge.length = io.readInt();

                a.edgeList.add(edge);
                b.edgeList.add(edge);
            }

            dfs1(nodes[1], null, 0);
            dfsn(nodes[n], null, 0);

            Node[] orderedNodes = nodes.clone();
            Arrays.sort(orderedNodes, 1, n + 1, (a, b) -> Long.compare(a.distn, b.distn));
            for (int i = 1; i <= n; i++) {
                orderedNodes[i].order = i;
            }

            long maxDist = 0;
            Deque<Node> queue = new ArrayDeque<>(n);
            Segment segment = Segment.build(1, n);
            for (int i = 1; i <= n; i++) {
                Node node = orderedNodes[i];

                int maxOrder;
                while ((maxOrder = Segment.query(1, n, segment)) != -1) {
                    Node max = orderedNodes[maxOrder];
                    if (max.father1 == node || node.father1 == max) {
                        queue.add(max);
                        Segment.update(maxOrder, 1, n, false, segment);
                    } else {
                        maxDist = Math.max(maxDist, node.dist1 + max.distn);
                        break;
                    }
                }

                while (!queue.isEmpty()) {
                    Segment.update(queue.removeFirst().order, 1, n, true, segment);
                }

                Segment.update(node.order, 1, n, true, segment);
            }

            for (int i = 0; i < m; i++) {
                long len = io.readInt();
                long shortest = Math.min(maxDist + len, nodes[1].distn);
                io.cache.append(shortest).append('\n');
            }
        }

        public static void dfs1(Node root, Node father, long length) {
            root.dist1 = length;
            root.father1 = father;

            for (Edge edge : root.edgeList) {
                Node other = edge.getOther(root);
                if (other == father) {
                    continue;
                }
                dfs1(other, root, length + edge.length);
            }
        }

        public static void dfsn(Node root, Node father, long length) {
            root.distn = length;
            root.fathern = father;

            for (Edge edge : root.edgeList) {
                Node other = edge.getOther(root);
                if (other == father) {
                    continue;
                }
                dfsn(other, root, length + edge.length);
            }
        }
    }

    public static class Segment implements Cloneable {
        Segment left;
        Segment right;
        boolean exist;

        public static Segment build(int l, int r) {
            Segment segment = new Segment();
            if (l != r) {
                int m = (l + r) >> 1;
                segment.left = build(l, m);
                segment.right = build(m + 1, r);
                segment.pushUp();
            }
            return segment;
        }

        public static boolean checkOutOfRange(int ll, int rr, int l, int r) {
            return ll > r || rr < l;
        }

        public static boolean checkCoverage(int ll, int rr, int l, int r) {
            return ll <= l && rr >= r;
        }

        public static void update(int x, int l, int r, boolean exist, Segment segment) {
            if (checkOutOfRange(x, x, l, r)) {
                return;
            }
            if (checkCoverage(x, x, l, r)) {
                segment.exist = exist;
                return;
            }
            int m = (l + r) >> 1;

            segment.pushDown();
            update(x, l, m, exist, segment.left);
            update(x, m + 1, r, exist, segment.right);
            segment.pushUp();
        }

        public static int query(int l, int r, Segment segment) {
            if (!segment.exist) {
                return -1;
            }
            while (l != r) {
                int m = (l + r) >> 1;
                if (segment.right.exist) {
                    l = m + 1;
                    segment = segment.right;
                } else if (segment.left.exist) {
                    segment = segment.left;
                    r = m;
                } else {
                    return -1;
                }
            }
            return l;
        }

        public void pushDown() {
        }

        public void pushUp() {
            exist = left.exist || right.exist;
        }

        @Override
        public Segment clone() {
            try {
                return (Segment) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }
    }


    public static class Node {
        int id;
        Node father1;
        Node fathern;
        long dist1;
        long distn;
        int order;

        List<Edge> edgeList = new ArrayList<>(1);

        @Override
        public String toString() {
            return "" + id;
        }
    }

    public static class Edge {
        Node src;
        Node dst;
        int length;

        Node getOther(Node me) {
            return me == src ? dst : src;
        }

        @Override
        public String toString() {
            return String.format("%s-%d->%s", src, length, dst);
        }
    }

    public static class FastIO {
        private final InputStream is;
        private final OutputStream os;
        private final Charset charset;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 8);
        public final StringBuilder cache = new StringBuilder();

        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastIO(InputStream is, OutputStream os, Charset charset) {
            this.is = is;
            this.os = os;
            this.charset = charset;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public double readDouble() {
            long num = readLong();
            if (next != '.') {
                return num;
            }

            next = read();
            long divisor = 1;
            long later = 0;
            while (next >= '0' && next <= '9') {
                divisor = divisor * 10;
                later = later * 10 + next - '0';
                next = read();
            }

            if (num >= 0) {
                return num + (later / (double) divisor);
            } else {
                return num - (later / (double) divisor);
            }
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public int readString(byte[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (byte) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public void flush() {
            try {
                os.write(cache.toString().getBytes(charset));
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public boolean hasMore() {
            skipBlank();
            return next != -1;
        }
    }

    public static class Memory {
        public static <T> void swap(T[] data, int i, int j) {
            T tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        public static <T> int min(T[] data, int from, int to, Comparator<T> cmp) {
            int m = from;
            for (int i = from + 1; i < to; i++) {
                if (cmp.compare(data[m], data[i]) > 0) {
                    m = i;
                }
            }
            return m;
        }

        public static <T> void move(T[] data, int from, int to, int step) {
            int len = to - from;
            step = len - (step % len + len) % len;
            Object[] buf = new Object[len];
            for (int i = 0; i < len; i++) {
                buf[i] = data[(i + step) % len + from];
            }
            System.arraycopy(buf, 0, data, from, len);
        }
    }
}