M. Доставка пиццы

В городе $m$ односторонних дорог. В $i$-й день направление $i$-й дороги меняется на противоположное, а вечером возвращается обратно. Пиццерия на перекрёстке 1, дом Алисы — на перекрёстке 2. Для каждого дня определите, станет ли кратчайший путь короче, не изменится или станет длиннее (в том числе если пути не станет вовсе).

В первой строке $n$ и $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$). В каждой из следующих $m$ строк — числа $a_i$, $b_i$ и $c_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 10^5$): дорога из $a_i$ в $b_i$, проезжаемая только в этом направлении. Несколько дорог могут соединять одну пару перекрёстков.

Гарантируется, что до начала эксперимента путь из вершины 1 в вершину 2 существует.

Выведите $m$ строк: HAPPY, если в $i$-й день путь станет короче, SOSO, если не изменится, и SAD, если станет длиннее либо исчезнет.