Untitled

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define all(a) begin(a),end(a)
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
const int mod=998244353;
const int inf=INT_MAX;
const int MAXN=100005;

vector<pair<int,pii>> Edge[MAXN],revEdge[MAXN];
vector<pii> edge;
bool shortestPath[MAXN];
int d1[MAXN],d2[MAXN],L[MAXN];
priority_queue<pii> q;
queue<int> qq;

inline void find_shortPath(){
	int now=2;
	do{
		for(auto i:revEdge[now]){
			if(d1[now]==d1[i.F]+i.S.F){
				now=i.F;
				shortestPath[i.S.S]=true;
				break;
			}
		}
	}while(now!=1);
}

int main(){
	cin.sync_with_stdio(0),cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=0;i<=n;i++){
		d1[i]=d2[i]=inf;
	}
	for(int i=0;i<m;i++){
		int u,v,l;
		cin >> u >> v >> l;
		Edge[u].pb({v,{l,i}});
		revEdge[v].pb({u,{l,i}});
		edge.pb({u,v});
		L[i]=l;
	}
	
	q.push({0,1});
	d1[1]=0;
	while(!q.empty()){
		pii now=q.top();q.pop();
		if(d1[now.S]<now.F) continue;

		for(auto i:Edge[now.S]){
			if(d1[now.S]+i.S.F<d1[i.F]){
				d1[i.F]=d1[now.S]+i.S.F;
				q.push({d1[i.F],i.F});
			}
		}
	}

	q.push({0,2});
	d2[2]=0;
	while(!q.empty()){
		pii now=q.top();q.pop();
		if(d2[now.S]<now.F) continue;

		for(auto i:revEdge[now.S]){
			if(d2[now.S]+i.S.F<d2[i.F]){
				d2[i.F]=d2[now.S]+i.S.F;
				q.push({d2[i.F],i.F});
			}
		}
	}

	find_shortPath();
	
	int ori=d1[2];
	for(int i=0;i<m;i++){
		int len=d1[edge[i].S]+d2[edge[i].F]+L[i];
		if(d1[edge[i].S]==inf || d2[edge[i].F]==inf) len=inf;
		if(len<ori) cout << "HAPPY\n";
		else if(len==ori || !shortestPath[i]) cout << "SOSO\n";
		else{
			qq.push(1);
			bool can_reach=false;
			while(!qq.empty()){
				int now=qq.front();qq.pop();
				if(now==2){
					can_reach=true;
					break;
				}
				for(auto j:Edge[now]){
					if(j.S.S==i || d1[now]+j.S.F!=d1[j.F]) continue;
					qq.push(j.F);
				}
			}
			if(can_reach) cout << "SOSO\n";
			else  cout << "SAD\n";
		}
	}
}