You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
There are $$$n$$$ railway stations in Berland. They are connected to each other by $$$n-1$$$ railway sections. The railway network is connected, i.e. can be represented as an undirected tree.

You have a map of that network, so for each railway section you know which stations it connects.

Each of the $$$n-1$$$ sections has some integer value of the scenery beauty. However, these values are not marked on the map and you don't know them. All these values are from $$$1$$$ to $$$10^6$$$ inclusive.

You asked $$$m$$$ passengers some questions: the $$$j$$$-th one told you three values:

- his departure station $$$a_j$$$;
- his arrival station $$$b_j$$$;
- minimum scenery beauty along the path from $$$a_j$$$ to $$$b_j$$$ (the train is moving along the shortest path from $$$a_j$$$ to $$$b_j$$$).

You are planning to update the map and set some value $$$f_i$$$ on each railway section — the scenery beauty. The passengers' answers should be consistent with these values.

Print any valid set of values $$$f_1, f_2, \dots, f_{n-1}$$$, which the passengers' answer is consistent with or report that it doesn't exist.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 5000$$$) — the number of railway stations in Berland.

The next $$$n-1$$$ lines contain descriptions of the railway sections: the $$$i$$$-th section description is two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n, x_i \ne y_i$$$), where $$$x_i$$$ and $$$y_i$$$ are the indices of the stations which are connected by the $$$i$$$-th railway section. All the railway sections are bidirected. Each station can be reached from any other station by the railway.

The next line contains a single integer $$$m$$$ ($$$1 \le m \le 5000$$$) — the number of passengers which were asked questions. Then $$$m$$$ lines follow, the $$$j$$$-th line contains three integers $$$a_j$$$, $$$b_j$$$ and $$$g_j$$$ ($$$1 \le a_j, b_j \le n$$$; $$$a_j \ne b_j$$$; $$$1 \le g_j \le 10^6$$$) — the departure station, the arrival station and the minimum scenery beauty along his path.

## Output Format
If there is no answer then print a single integer -1.

Otherwise, print $$$n-1$$$ integers $$$f_1, f_2, \dots, f_{n-1}$$$ ($$$1 \le f_i \le 10^6$$$), where $$$f_i$$$ is some valid scenery beauty along the $$$i$$$-th railway section.

If there are multiple answers, you can print any of them.

## Examples
```input
4
1 2
3 2
3 4
2
1 2 5
1 3 3
```
```output
5 3 5
```
-----
```input
6
1 2
1 6
3 1
1 5
4 1
4
6 1 3
3 4 1
6 5 2
1 2 5
```
```output
5 3 1 2 1
```
-----
```input
6
1 2
1 6
3 1
1 5
4 1
4
6 1 1
3 4 3
6 5 3
1 2 4
```
```output
-1
```

Now solve the problem and return the code.