Untitled

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(“Ofast,no-stack-protector,unroll-loops,fast-math”)
#pragma GCC target(“fma,sse,sse2,sse3,sse4”)
#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(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";
		}
	}
}