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.util.*;
import java.io.*;

public class A {
	
	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		//find shortest path
		/*
		if any node along the shortest path contains 2 or more nodes, take that, distance never changes
		
		otherwise, all nodes on the shortest path have a subtree of size at most 1
		you are only ever going to take the deepest in any subtree
		find the distance to the deepest part of every subtree
		iterate backwards, storing the farthest one.
		dist=max(dist, distFromStartToMyDeepest+distFromOtherDeepestToFinish)
		
		*/
		PrintWriter out=new PrintWriter(System.out);
		int n=fs.nextInt(), q=fs.nextInt();
		ArrayList<Edge>[] adj=new ArrayList[n];
		for (int i=0; i<n; i++) adj[i]=new ArrayList<>();
		for (int i=1; i<n; i++) {
			int from=fs.nextInt()-1, to=fs.nextInt()-1, cost=fs.nextInt();
			adj[from].add(new Edge(to, cost));
			adj[to].add(new Edge(from, cost));
		}
		
		long[] from0=bfs(adj, n, 0);
		long[] fromN=bfs(adj, n, n-1);
		long diam=fromN[0];
		boolean[] isOnDiam=new boolean[n];
		for (int i=0; i<n; i++) isOnDiam[i]=from0[i]+fromN[i]==diam;
		ArrayList<DiamNode> diamNodes=new ArrayList<>();
		for (int i=0; i<n; i++) if (isOnDiam[i]) diamNodes.add(new DiamNode(i, from0[i]));
		Collections.sort(diamNodes);
		
		int[] nodeIndexInDiam=new int[diamNodes.size()];
		for (int i=0; i<diamNodes.size(); i++) 
			nodeIndexInDiam[i]=diamNodes.get(i).index;
		int[] spotInDiam=new int[n];
		for (int i=0; i<nodeIndexInDiam.length; i++)
			spotInDiam[nodeIndexInDiam[i]]=i;
		
		int[] marks=new int[n];
		Arrays.fill(marks, -1);
		for (int i:nodeIndexInDiam)
			markBFS(adj, n, marks, i, isOnDiam);
		int[] numMarkedWith=new int[n];
		for (int i:marks)
			numMarkedWith[i]++;
		
		long bestOtherDiam=0;
		for (int i:numMarkedWith)
			if (i>2)
				bestOtherDiam=diam;
		
		long[] farthestTotal=new long[nodeIndexInDiam.length];
		for (int i=0; i<n; i++)
			farthestTotal[spotInDiam[marks[i]]]=Math.max(farthestTotal[spotInDiam[marks[i]]], from0[i]+fromN[i]);
		
		long[] maxDistFromStart=new long[nodeIndexInDiam.length], maxDistFromEnd=new long[nodeIndexInDiam.length];
		for (int i=0; i<nodeIndexInDiam.length; i++) {
			maxDistFromStart[i]=(farthestTotal[i]-diam)/2+from0[nodeIndexInDiam[i]];
			maxDistFromEnd[i]=(farthestTotal[i]-diam)/2+fromN[nodeIndexInDiam[i]];
		}
		int oldBest=nodeIndexInDiam.length-1;
		int secondOldBest=-1;
		if (numMarkedWith[nodeIndexInDiam[oldBest]]!=1) secondOldBest=oldBest;
		
		for (int i=oldBest-1; i>=0; i--) {
			if (numMarkedWith[nodeIndexInDiam[i]]==1) {
				if (oldBest==i+1) {
					if (secondOldBest!=-1) {
						bestOtherDiam=Math.max(bestOtherDiam, maxDistFromStart[i]+maxDistFromEnd[secondOldBest]);
					}
				}
				else {
					bestOtherDiam=Math.max(bestOtherDiam, maxDistFromStart[i]+maxDistFromEnd[oldBest]);
				}
				secondOldBest=oldBest;
				if (maxDistFromEnd[i]>maxDistFromEnd[oldBest])
					oldBest=i;
			}
			else {
				bestOtherDiam=Math.max(bestOtherDiam, maxDistFromStart[i]+maxDistFromEnd[oldBest]);
				if (maxDistFromEnd[i]>maxDistFromEnd[oldBest])
					secondOldBest=oldBest=i;
			}
		}
		
		//answer queries
		for (int i=0; i<q; i++) {
			long dist=fs.nextInt();
			out.println(Math.min(diam, dist+bestOtherDiam));
		}
		out.close();
		
		//System.out.println("On diam: "+Arrays.toString(isOnDiam));
		//System.out.println("NumMarkedWith: "+Arrays.toString(numMarkedWith));
		//System.out.println("max dist from start: "+Arrays.toString(maxDistFromStart));
		//System.out.println("max dist from end: "+Arrays.toString(maxDistFromEnd));
	}
	
	private static long[] bfs(ArrayList<Edge>[] adj, int n, int from) {
		long[] dist=new long[n];
		ArrayDeque<Integer> bfs=new ArrayDeque<>();
		Arrays.fill(dist, -1);
		dist[from]=0;
		bfs.add(from);
		while (!bfs.isEmpty()) {
			int next=bfs.remove();
			for (Edge e:adj[next]) {
				if (dist[e.to]!=-1) continue;
				dist[e.to]=dist[next]+e.cost;
				bfs.add(e.to);
			}
		}
		return dist;
	}
	
	private static void markBFS(ArrayList<Edge>[] adj, int n, int[] marks, int from, boolean[] isOnDiam) {
		ArrayDeque<Integer> bfs=new ArrayDeque<>();
		bfs.add(from);
		marks[from]=from;
		while (!bfs.isEmpty()) {
			int next=bfs.remove();
			for (Edge e:adj[next]) {
				if (isOnDiam[e.to]||marks[e.to]!=-1)
					continue;
				marks[e.to]=from;
				bfs.add(e.to);
			}
		}
	}
	
	static class DiamNode implements Comparable<DiamNode> {
		int index;
		long distFromStart;
		
		public DiamNode(int index, long distFromStart) {
			this.index=index;
			this.distFromStart=distFromStart;
		}
		
		public int compareTo(DiamNode o) {
			return Long.compare(distFromStart, o.distFromStart);
		}
	}
	
	private static class Edge {
		int to, cost;
		
		public Edge(int to, int cost) {
			this.to=to;
			this.cost=cost;
		}
	}

	private static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++)
				a[i]=nextInt();
			return a;
		}
		long[] readLongArray(int n) {
			long[] a=new long[n];
			for (int i=0; i<n; i++)
				a[i]=nextLong();
			return a;
		}
	}
}