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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

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

    static final class TaskF {
        List<TaskF.Edge>[] tree;
        List<Integer> path = new ArrayList<>();

        public void solve(int __, InputReader in, PrintWriter out) {
            int vertices = in.nextInt();
            int count = in.nextInt();
            int[] degree = new int[vertices];
            //noinspection unchecked
            tree = new List[vertices];
            for (int i = 0; i < vertices; ++i) {
                tree[i] = new ArrayList<>();
            }
            for (int e = 0; e < vertices - 1; ++e) {
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                TaskF.Edge edge = new TaskF.Edge(u, v, in.nextInt());
                tree[u].add(edge);
                tree[v].add(edge);
                degree[u]++;
                degree[v]++;
            }
            int[] lengthes = in.nextIntArray(count);
            dfs(0, -1);
            long baseDistance = 0;
            for (int i = 1; i < path.size(); ++i) {
                baseDistance += distanceBetween(path.get(i - 1), path.get(i));
            }
            boolean uselessCycle = false;
            int degThree = 0;
            for (int v = 0; v < vertices; ++v) {
                if (degree[v] > 3) {
                    uselessCycle = true;
                } else if (degree[v] == 3) {
                    degThree++;
                }
            }
            for (int i = 1; i < path.size() - 1; ++i) {
                if (degree[path.get(i)] == 3) {
                    degThree--;
                }
            }
            if (degThree != 0) {
                uselessCycle = true;
            }
            if (uselessCycle) {
                for (int i = 0; i < count; ++i) {
                    out.println(baseDistance);
                }
                return;
            } // else all vertices have degree <= 3 (degree == 3 is possible only on path between 1 and n);
            long[] pre = new long[path.size()];
            long[] suf = new long[path.size()];
            boolean[] hasBranch = new boolean[path.size()];
            for (int i = 1; i < path.size(); ++i) {
                int j = path.size() - 1 - i;
                pre[i] = pre[i - 1] + distanceBetween(path.get(i), path.get(i - 1));
                suf[j] = suf[j + 1] + distanceBetween(path.get(j), path.get(j + 1));
            }
            for (int i = 0; i < path.size(); ++i) {
                long ad = dfs(path.get(i), i > 0 ? path.get(i - 1) : -1, i + 1 < path.size() ? path.get(i + 1) : -1);
                pre[i] += ad;
                suf[i] += ad;
                hasBranch[i] = ad > 0;
            }
            for (int i = 1; i < path.size(); ++i) {
                int j = path.size() - 1 - i;
                pre[i] = Math.max(pre[i], pre[i - 1]);
                suf[j] = Math.max(suf[j], suf[j + 1]);
            }
            long best = 0;
            for (int i = 1; i < path.size(); ++i) {
                if (hasBranch[i - 1] || hasBranch[i]) {
                    best = Math.max(best, pre[i - 1] + suf[i]);
                } else {
                    if (i > 1) {
                        best = Math.max(best, pre[i - 2] + suf[i]);
                    }
                    if (i + 1 < path.size()) {
                        best = Math.max(best, pre[i - 1] + suf[i + 1]);
                    }
                }
            }
            for (int length : lengthes) {
                out.println(Math.min(baseDistance, best + length));
            }
        }

        private long distanceBetween(int u, int v) {
            for (TaskF.Edge edge : tree[u]) {
                if (edge.opposite(u) == v) {
                    return edge.weight;
                }
            }
            throw new IllegalArgumentException("there's no edge between " + u + " " + v);
        }

        private long dfs(int vertex, int neightbour1, int neightbour2) {
            for (TaskF.Edge edge : tree[vertex]) {
                int next = edge.opposite(vertex);
                if (next != neightbour1 && next != neightbour2) {
                    return edge.weight + dfs(next, vertex, -1);
                }
            }
            return 0;
        }

        private boolean dfs(int vertex, int parent) {
            if (vertex == tree.length - 1) {
                path.add(vertex);
                return true;
            }
            for (TaskF.Edge edge : tree[vertex]) {
                int next = edge.opposite(vertex);
                if (next != parent) {
                    if (dfs(next, vertex)) {
                        path.add(vertex);
                        return true;
                    }
                }
            }
            return false;
        }

        static class Edge {
            final int u;
            final int v;
            final int weight;

            Edge(int u, int v, int weight) {
                this.u = u;
                this.v = v;
                this.weight = weight;
            }

            int opposite(int from) {
                return from ^ u ^ v;
            }

        }

    }

    static class InputReader {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

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

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

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

        public String readLine() {
            String line;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
    }
}