A. Edgy Graph
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges, where each edge has a positive weight.

Your task is to construct an array $$$a$$$ of size $$$n$$$ such that the following conditions are satisfied:

  • $$$1 \le a_i \le 10^9$$$ for all $$$1 \le i \le n$$$
  • for every edge $$$(u, v)$$$ between vertices $$$u$$$ and $$$v$$$ having weight $$$w$$$, $$$\max(a_u, a_v) = w$$$. That is, the maximum value of the two vertices of the edge must be equal to the weight of the edge.
Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$) — the number of vertices and the number of edges in the graph.

The next $$$m$$$ lines describe the edges. Each line contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \le u, v \le n$$$, $$$1 \le w \le 10^9$$$) — the vertices connected by the edge and its weight. It is guaranteed that the graph has no self-loops or multiple edges.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single line containing $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the array $$$a$$$ that satisfies the given conditions. If there are multiple such arrays, output any of them. If no such array exists, output $$$-1$$$ instead.

Example
Input
3
3 3
1 2 1
2 3 2
3 1 2
3 3
1 2 1
2 3 2
1 3 3
3 1
1 2 5
Output
1 1 2
-1
1 5 1000000000