#include <bits/stdc++.h>
                                        #include<iostream>
                                        #include<cstdio>
                                        #include<vector>
                                        #include<queue>
                                        #include<map>
                                        #include<cstring>
                                        #include<string>
                                        #include <math.h>
                                        #include<algorithm>
                                    //    #include <boost/multiprecision/cpp_int.hpp>
                                        #include<functional>
                                #define int long long
                                        #define inf  1000000007
                                        #define pa pair<int,int>
                                        #define ll long long
                                        #define pal pair<double,pa>
                                        #define ppa pair<int,int>
                                        #define ppap pair<pa,pa>
                                        #define ssa pair<string,int>
                                        #define  mp make_pair
                                        #define  pb push_back
                                        #define EPS (1e-10)
                                        #define equals(a,b) (fabs((a)-(b))<EPS)
                                  #define VI vector<int>
                                        using namespace std;
 
int par[500100],ranks[500100],kosuu[500100];     
 
void shoki(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
        ranks[i]=0;
        kosuu[i]=1;
    }
}
 
int root(int x){
    return par[x]==x ? x : par[x]=root(par[x]);
}
 
bool same(int x,int y){
return root(x)==root(y);
}
 
void unite(int x,int y){
 x=root(x);
 y=root(y);
    int xx=kosuu[x],yy=kosuu[y];
 if(x==y) return;
    if(ranks[x]<ranks[y]){
        par[x]=y;
        kosuu[y]=yy+xx;
    }
 else {
    par[y]=x;
    if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
    kosuu[x]=yy+xx;
 }
    return;
}
 
int gcd(int a1,int a2){
    if(a1<a2) return gcd(a2,a1);
    if(a2==1) return 1;
    if(a1%a2==0) return a2;
    return gcd(a2,a1%a2);
}
 
 
int rui2(int e,int r){
    if(r==0) return 1;
    if(r==1) return e%inf;
    if(r%2==1) return (e*rui2(e,r-1))%inf;
    int w=rui2(e,r/2)%inf;
    return (w*w)%inf;
}
 
int inf2=1000000000ll*100000ll;
int n,m;
vector<pa>G[100030],G2[100030];
vector<int> dag[100030],dag2[100030];
int s1[100030],s2[100030],a[100030],b[100030],c[100030];
int ans[100030]={0};
bool sumi[100030]={0};
priority_queue<pa,vector<pa>,greater<pa>> pq;
int nyu[100030]={0},shu[100030]={0};
int ok[100030]={0};
 
 
vector<int> topo;
int jisuu[100030]={0};
 
int hashi[100030]={0};
int dagk1[100030]={0},dagk2[100030]={0};
 
void dagkosuu(int u){
    if(dagk1[u])return;
    int ans=0;
    for(auto v:dag2[u])ans+=dagk1[v],ans%=inf;
    dagk1[u]=ans%inf;
}
 
void dagkosuu2(int u){
    if(dagk2[u])return;
    int ans=0;
    for(auto v:dag[u])ans+=dagk2[v],ans%=inf;
    dagk2[u]=ans%inf;
}
 
 
void toporoji(){
     
    queue<int> qu;
    qu.push(1);
     
    for(int i=1;i<=n;i++)for(auto v:dag[i])jisuu[v]++;
     
    while(qu.size()>0){
        int r=qu.front();
        qu.pop();
        topo.pb(r);
         
        for(auto v:dag[r]){
            jisuu[v]--;
            if(jisuu[v]==0) qu.push(v);
        }
    }
     
}
 
bool  check(int i){
    return (dagk1[a[i]]*dagk2[b[i]])%inf==dagk1[2]%inf;
     
}
  
  
int dfsb( vector<pa>& res, int v, int& count, int from, VI& low, VI& pre) {
  pre[v] = count++;
  low[v] = pre[v];
	bool bbb=false;
  for (auto it = dag[v].begin(); it != dag[v].end(); it++) {
    int to = *it;
  //    bool b=false;
    if (pre[to] == -1) {
      // destination has not been visited
      // visit destination and update low[v]
      low[v] = min(low[v], dfsb( res, to, count, v, low, pre));
      if (low[to] == pre[to]) {
        // edge is not contained in a closed path -> bridge
        res.pb(mp(v, to));
      }
    } else {
      if (from == to &&!bbb) {
       bbb=1;
        // ignore a path to parent
        continue;
      }
      low[v] = min(low[v], low[to]);
    }
  }
  return low[v];
}
 
 
vector<pa> bridges(int V) {
  vector<pa> res;
  if (V > 0) {
    // assume at least the first vertex exists
    vector<int> low(V+1, -1);  // lowest reacheable index
    vector<int> pre(V+1, -1);  // pre-order index
    int count = 0;  // pre-order index counter
    dfsb(res, 1, count, -1, low, pre);  // start dfs from vertex 0
  }
  return res;
}
set<pa> se;
  
            signed main(){
   cin>>n>>m;
                for(int i=0;i<m;i++){
                int y,yy,yyy;
                    cin>>y>>yy>>yyy;
                    G[y].pb(mp(yy,yyy));
                    G2[yy].pb(mp(y,yyy));
                    a[i]=y;
                    b[i]=yy;
                    c[i]=yyy;
                 
                }
                for(int i=0;i<n+10;i++)sumi[i]=0,s1[i]=inf2;
                pq.push(mp(0,1));
                while(pq.size()){
                    pa z=pq.top();
                    pq.pop();
                    if(sumi[z.second])continue;
                    s1[z.second]=z.first;
                    sumi[z.second]=1;
                    for(auto v:G[z.second])pq.push(mp(z.first+v.second,v.first));
                }
                for(int i=0;i<n+10;i++)sumi[i]=0,s2[i]=inf2;
                pq.push(mp(0,2));
                while(pq.size()){
                    pa z=pq.top();
                    pq.pop();
                    if(sumi[z.second])continue;
                    s2[z.second]=z.first;
                    sumi[z.second]=1;
                    for(auto v:G2[z.second])pq.push(mp(z.first+v.second,v.first));
                }
                 
                int len=s1[2];
                 
                for(int i=0;i<m;i++){
                    if(s1[a[i]]+s2[b[i]]+c[i]==len){
                        dag[a[i]].pb(b[i]);
                        dag[b[i]].pb(a[i]);
                         
                //      cout<<"dag "<<a[i]<<" "<<b[i]<<endl;
                     
                    }
                    else{
                        if(s1[b[i]]+s2[a[i]]+c[i]<len)ans[i]=1;
                        else ans[i]=3;
                         
                         
                    }
                     
                }
            //  saiki(1);
                vector<pa> w=bridges(n);
                for(auto v:w){
                //  cout<<v.first<<" "<<v.second<<endl;
                    se.insert(v);
                    swap(v.first,v.second);
                    se.insert(v);
                }
                for(int i=0;i<m;i++){
                    if(ans[i])continue;
           //       cout<<a[i]<<" "<<b[i]<<endl;
                    if(se.find(mp(a[i],b[i]))!=se.end()) ans[i]=2;
                    else ans[i]=3;
                     
                }
                 
                for(int i=0;i<m;i++){
                    if(ans[i]==1)cout<<"HAPPY"<<endl;
                    if(ans[i]==2)cout<<"SAD"<<endl;
                    if(ans[i]==3)cout<<"SOSO"<<endl;
                }
            }

Measured memory_bytes: 53004