The Berland Kingdom is a set of n cities connected with each other with n - 1 railways. Each road connects exactly two different cities. The capital is located in city 1. For each city there is a way to get from there to the capital by rail.

In the i-th city there is a soldier division number i, each division is characterized by a number of ai. It represents the priority, the smaller the number, the higher the priority of this division. All values of ai are different.

One day the Berland King Berl Great declared a general mobilization, and for that, each division should arrive in the capital. Every day from every city except the capital a train departs. So there are exactly n - 1 departing trains each day. Each train moves toward the capital and finishes movement on the opposite endpoint of the railway on the next day. It has some finite capacity of cj, expressed in the maximum number of divisions, which this train can transport in one go. Each train moves in the direction of reducing the distance to the capital. So each train passes exactly one railway moving from a city to the neighboring (where it stops) toward the capital.

In the first place among the divisions that are in the city, division with the smallest number of ai get on the train, then with the next smallest and so on, until either the train is full or all the divisions are be loaded. So it is possible for a division to stay in a city for a several days.

The duration of train's progress from one city to another is always equal to 1 day. All divisions start moving at the same time and end up in the capital, from where they don't go anywhere else any more. Each division moves along a simple path from its city to the capital, regardless of how much time this journey will take.

Your goal is to find for each division, in how many days it will arrive to the capital of Berland. The countdown begins from day 0.

Input

The first line contains the single integer n (1 ≤ n ≤ 5000). It is the number of cities in Berland. The second line contains n space-separated integers a1, a2, ..., an, where ai represents the priority of the division, located in the city number i. All numbers a1, a2, ..., an are different (1 ≤ ai ≤ 109). Then n - 1 lines contain the descriptions of the railway roads. Each description consists of three integers vj, uj, cj, where vj, uj are number of cities connected by the j-th rail, and cj stands for the maximum capacity of a train riding on this road (1 ≤ vj, uj ≤ n, vj ≠ uj, 1 ≤ cj ≤ n). 

Output

Print sequence t1, t2, ..., tn, where ti stands for the number of days it takes for the division of city i to arrive to the capital. Separate numbers with spaces.

Examples

Input

4
40 10 30 20
1 2 1
2 3 1
4 2 1


Output

0 1 3 2 

Input

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


Output

0 1 4 2 3 
import java.util.InputMismatchException;
import java.math.BigInteger;
import java.util.Stack;
import java.util.*;
import java.util.List;
import java.util.Iterator;
import java.util.Comparator;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.NavigableSet;
import java.util.Map;
import java.util.Collections;
import java.util.HashMap;
import java.util.Collection;
import java.util.ArrayList;
import java.io.*;

/**
 * Generated by Contest helper plug-in
 * Actual solution is at the bottom
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new StreamInputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		run(in, out);
	}

	public static void run(InputReader in, PrintWriter out) {
		Solver solver = new TaskC();
		solver.solve(1, in, out);
		Exit.exit(in, out);
	}
}

abstract class InputReader {
	private boolean finished = false;

	public abstract int read();

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuffer res = new StringBuffer();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public void setFinished(boolean finished) {
		this.finished = finished;
	}

	public abstract void close();
}

class StreamInputReader extends InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar, numChars;

	public StreamInputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	@Override
	public void close() {
		try {
			stream.close();
		} catch (IOException ignored) {
		}
	}
}

class Exit {
	private Exit() {
	}

	public static void exit(InputReader in, PrintWriter out) {
		in.setFinished(true);
		in.close();
		out.close();
	}
}

interface Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out);
}

class ArrayUtils {
	public static Integer[] generateOrder(int size) {
		Integer[] order = new Integer[size];
		for (int i = 0; i < size; i++)
			order[i] = i;
		return order;
	}

	public static Integer[] order(int size, Comparator<Integer> comparator) {
		Integer[] order = generateOrder(size);
		Arrays.sort(order, comparator);
		return order;
	}
}

abstract class ReadOnlyIterator<T> implements Iterator<T>  {
	public final void remove() {
		throw new UnsupportedOperationException();
	}
}

class IOUtils {
	public static void printArray(int[] array, PrintWriter out) {
		if (array.length == 0) {
			out.println();
			return;
		}
		out.print(array[0]);
		for (int i = 1; i < array.length; i++)
			out.print(" " + array[i]);
		out.println();
	}

	public static<T> void printCollection(Iterable<T> collection, PrintWriter out, String delimiter) {
		boolean isFirst = true;
		for (T element : collection) {
			if (isFirst)
				isFirst = false;
			else
				out.print(delimiter);
			out.print(element);
		}
		out.println();
	}

	public static int[] readIntArray(InputReader in, int size) {
		int[] array = new int[size];
		for (int i = 0; i < size; i++)
			array[i] = in.readInt();
		return array;
	}

	public static void readIntArrays(InputReader in, int[]... arrays) {
		for (int i = 0; i < arrays[0].length; i++) {
			for (int j = 0; j < arrays.length; j++)
				arrays[j][i] = in.readInt();
		}
	}

	}

abstract class AbstractSequence<T> implements Sequence<T> {

	public Iterator<T> iterator() {
		return new ReadOnlyIterator<T>() {
			private int index = 0;

			public boolean hasNext() {
				return index != size();
			}

			public T next() {
				if (!hasNext())
					throw new NoSuchElementException();
				return get(index++);
			}
		};
	}

	@Override
	public String toString() {
		StringWriter writer = new StringWriter();
		IOUtils.printCollection(this, new PrintWriter(writer), ",");
		return "[" + writer.toString().substring(0, writer.toString().length() - 1) + "]";
	}

	}

abstract class AbstractWritableSequence<T> extends AbstractSequence<T> implements WritableSequence<T> {

	}

abstract class ArrayWrapper<T> extends AbstractWritableSequence<T> {

	public static WritableSequence<Integer> wrap(int...array) {
		return new IntArrayWrapper(array);
	}

	protected static class IntArrayWrapper extends ArrayWrapper<Integer> {
		protected final int[] array;

		protected IntArrayWrapper(int[] array) {
			this.array = array;
		}

		public int size() {
			return array.length;
		}

		public Integer get(int index) {
			return array[index];
		}

		}

	}

interface Sequence<T> extends Iterable<T> {
	public int size();
	public T get(int index);
}

class SequenceUtils {

	public static Integer[] order(final Sequence<? extends Comparable<?>>...sequences) {
		return ArrayUtils.order(sequences[0].size(), new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				for (Sequence<? extends Comparable> sequence : sequences) {
					//noinspection unchecked
					int value = sequence.get(o1).compareTo(sequence.get(o2));
					if (value != 0)
						return value;
				}
				return 0;
			}
		});
	}

	}

interface WritableSequence<T> extends Sequence<T> {
	}

class GraphUtils {
	public static int[][] buildGraph(int vertexCount, int[] from, int[] to) {
		int edgeCount = from.length;
		int[] degree = new int[vertexCount];
		for (int i = 0; i < edgeCount; i++) {
			degree[from[i]]++;
			degree[to[i]]++;
		}
		int[][] graph = new int[vertexCount][];
		for (int i = 0; i < vertexCount; i++)
			graph[i] = new int[degree[i]];
		for (int i = 0; i < edgeCount; i++) {
			graph[from[i]][--degree[from[i]]] = i;
			graph[to[i]][--degree[to[i]]] = i;
		}
		return graph;
	}

	public static int otherVertex(int vertex, int from, int to) {
		return from + to - vertex;
	}

	}

class TaskC implements Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
		int cityCount = in.readInt();
		int[] priority = IOUtils.readIntArray(in, cityCount);
		int[] from = new int[cityCount - 1];
		int[] to = new int[cityCount - 1];
		int[] capacity = new int[cityCount - 1];
		IOUtils.readIntArrays(in, from, to, capacity);
		for (int i = 0; i < cityCount - 1; i++) {
			from[i]--;
			to[i]--;
		}
		int[][] graph = GraphUtils.buildGraph(cityCount, from, to);
		int[] parent = new int[cityCount];
		int[] size = new int[cityCount];
		int[] capacityUp = new int[cityCount];
		capacityUp[0] = Integer.MAX_VALUE;
		calculate(graph, 0, -1, parent, size, from, to, capacityUp, capacity);
		int[][] remainingCapacity = new int[cityCount][];
		for (int i = 0; i < cityCount; i++) {
			remainingCapacity[i] = new int[size[i]];
			Arrays.fill(remainingCapacity[i], capacityUp[i]);
		}
		Integer[] order = SequenceUtils.order(ArrayWrapper.wrap(priority));
		int[] answer = new int[cityCount];
		for (int i : order) {
			int vertex = i;
			int day = 0;
			while (vertex != 0) {
				if (remainingCapacity[vertex][day] != 0) {
					remainingCapacity[vertex][day]--;
					vertex = parent[vertex];
				}
				day++;
			}
			answer[i] = day;
		}
		IOUtils.printArray(answer, out);
	}

	private int calculate(int[][] graph, int vertex, int last, int[] parent, int[] size, int[] from, int[] to, int[] capacityUp, int[] capacity) {
		parent[vertex] = last;
		size[vertex] = 1;
		for (int edge : graph[vertex]) {
			int nextVertex = GraphUtils.otherVertex(vertex, from[edge], to[edge]);
			if (nextVertex == last)
				continue;
			capacityUp[nextVertex] = capacity[edge];
			size[vertex] += calculate(graph, nextVertex, vertex, parent, size, from, to, capacityUp, capacity);
		}
		return size[vertex];
	}
}

