피자 배달

앨리사는 뉴 츠쿠바 시에 사는 대학생이다. 이 도시의 도로 구간은 모두 일방통행이다. 내일부터 시작하는 사회 실험에서는 하루에 한 구간씩, 인접한 두 교차로를 잇는 도로 구간 하나를 골라 통행 방향을 반대로 바꾼다. 나머지 구간의 방향은 그대로 두며, 바꾼 방향은 다음 날 원래대로 돌아온다. $i$번째 날에 방향이 뒤집히는 구간은 $i$번 구간이다.

앨리사는 매일 같은 가게에서 피자를 주문한다. 피자는 가게가 있는 교차로에서 앨리사의 집이 있는 교차로까지 최단 경로를 따라 배달된다.

통행 방향이 바뀌면 최단 경로가 달라질 수 있다. 이 실험이 배달 경로에 어떤 영향을 주는지 날마다 판정하자.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

n m
a1 b1 c1
.
.
.
am bm cm

첫 줄에는 교차로의 수 $n$과 도로 구간의 수 $m$이 주어진다 ($2 \le n \le 100000$, $1 \le m \le 100000$). 교차로에는 $1$번부터 $n$번까지, 도로 구간에는 $1$번부터 $m$번까지 번호가 붙어 있다.

이어지는 $m$개의 줄에는 도로 구간 정보가 세 정수 $a_i$, $b_i$, $c_i$로 주어진다 ($1 \le a_i \le n$, $1 \le b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 100000$). $i$번 구간은 교차로 $a_i$에서 교차로 $b_i$로 향하는 일방통행 도로이고 길이는 $c_i$이며, $i$번째 날에 방향이 뒤집힌다. 같은 교차로 쌍을 잇는 구간이 둘 이상 있을 수 있다.

피자 가게는 $1$번 교차로에, 앨리사의 집은 $2$번 교차로에 있다. 실험이 시작되기 전에 가게에서 집으로 가는 경로가 적어도 하나 있음이 보장된다.

$m$개의 줄을 출력한다. $i$번째 줄에는 다음을 출력한다.

• $i$번째 날의 최단 경로가 더 짧아지면 HAPPY
• $i$번째 날의 최단 경로 길이가 그대로이면 SOSO
• $i$번째 날의 최단 경로가 더 길어지거나 가게에서 집으로 가는 경로가 사라지면 SAD

배달 오토바이가 가게로 돌아갈 수 있는지는 따지지 않는다.