You are given an undirected weighted graph with \(n\) vertices and \(m\) edges.

Consider all shortest paths between vertices \(1\) and \(n\), for any vertex such as \(v\ (1 \le v \le n)\), say that, if \(v\) is in either all shortest paths or some of them or none of them.

Input format

The first line contains two integers \(n, m\) denoting the number of the graph's vertices and edges respectively.
Each of the following \(m\) lines contains space-separated \(v_i, u_i\), and \(w_i\) describing the graph's \(i^{th}\) edge's vertices (\(v_i, u_i\)) and its weight (\(w_i\)).

Output format

Print \(n\) lines where the \(i^{th}\) line contains either \(all\) if vertex \(i\) is in all shortest paths between \(1\) to \(n\) or \(some\) if vertex \(i\) is in some of shortest paths or \(none\) otherwise.

Constraints

\(1 \leq n \leq 2 \times 10^5 \\ 1 \leq m \leq 3 \times 10^5\)

\(1 \leq v_i, u_i \leq n \\ 1 \leq w_i \leq 10^9\)

It is guaranteed that there are no multiple edges or self-loops in the graph.
Also, it is guaranteed that the graph is connected.