Pizza Delivery
题号：NC239230
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给你一个n个节点m个边的有向图，我们规定节点1为起点，节点2为终点。

接下来有m天，第i天期间第i条边的方向会反向（第i天结束后会变回来），现在请你在每一天，计算从起点到终点的最短路如何变化。

输入描述:

第一行两个整数n,m
接下来m行每行三个整数a,b,c，表示一条从a到b长度为c的边。

输出描述:

m行，第i行表示第i天最短路的变化情况，如果最短路变短了则输出"HAPPY"，不变输出"SOSO"，变长了或者无法到达输出"SAD"(均不含引号)。
示例1

输入

复制 
4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12

输出

复制 
SAD
SAD
SAD
SOSO
HAPPY
示例2

输入

复制 
7 5
1 3 2
1 6 3
4 2 4
6 2 5
7 5 6

输出

复制 
SOSO
SAD
SOSO
SAD
SOSO
示例3

输入

复制 
10 14
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 11
5 8 12
6 10 6
7 10 8
8 3 6

输出

复制 
SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD

备注: