Language: C++

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
#include <tuple>
#include <map>

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 16;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}


struct CostGraph {
    using T = ll;
    CostGraph(const int v) : V{v}
    {
        edge.resize(v);
        rev_edge.resize(v);
    }
    struct Edge {
        Edge() {}
        Edge(const int from, const int to, const T cost) : from{from}, to{to}, cost{cost} {}
        int from;
        int to;
        T cost;
        bool operator<(const Edge& e) const
        {
            return cost != e.cost ? cost < e.cost : to < e.to;
        }
    };
    void addEdge(const int from, const int to, const T cost)
    {
        edge[from].push_back(Edge{from, to, cost});
        rev_edge[to].push_back(Edge{to, from, cost});
    }
    vector<vector<Edge>> edge;
    vector<vector<Edge>> rev_edge;
    const int V;
};


void Dijkstra(const CostGraph& g, const int s, vector<CostGraph::T>& d)
{
    using T = CostGraph::T;
    assert(s < g.V);
    assert(d.size() == g.V);
    using P = pair<T, int>;
    priority_queue<P, vector<P>, greater<P>> q;
    for (int i = 0; i < g.V; i++) {
        d[i] = INF<T>;
    }
    d[s] = 0;
    q.push(make_pair(0, s));
    while (not q.empty()) {
        const P& p = q.top();
        const T cost = p.first;
        const int v = p.second;
        q.pop();
        if (d[v] < cost) {
            continue;
        }
        for (const auto& e : g.edge[v]) {
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push(make_pair(d[e.to], e.to));
            }
        }
    }
}
void ReverseDijkstra(const CostGraph& g, const int s, vector<CostGraph::T>& d)
{
    using T = CostGraph::T;
    assert(s < g.V);
    assert(d.size() == g.V);
    using P = pair<T, int>;
    priority_queue<P, vector<P>, greater<P>> q;
    for (int i = 0; i < g.V; i++) {
        d[i] = INF<T>;
    }
    d[s] = 0;
    q.push(make_pair(0, s));
    while (not q.empty()) {
        const P& p = q.top();
        const T cost = p.first;
        const int v = p.second;
        q.pop();
        if (d[v] < cost) {
            continue;
        }
        for (const auto& e : g.rev_edge[v]) {
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

class BiconnectedComponent
{
public:
    BiconnectedComponent(const CostGraph& g_) : num{0}, comp_num{0}, size{g_.V}, bridge(0), ord(size, -1), low(size, 0), comp(size, -1)
    {
        for (int i = 0; i < size; i++) {
            bridge_dfs(g_, i);
        }
        for (int i = 0; i < size; i++) {
            if (comp[i] >= 0) {
                continue;
            }
            comp_dfs(g_, i, comp_num);
            comp_num++;
        }
    }

    CostGraph toTree() const
    {
        CostGraph tree(comp_num);
        for (const auto& e : bridge) {
            tree.addEdge(comp[e.from], comp[e.to], 1);
            tree.addEdge(comp[e.to], comp[e.from], 1);
        }
        return tree;
    }
    const vector<CostGraph::Edge>& getEdge() const
    {
        return bridge;
    }
    bool isBridge(const int i, const int j) const
    {
        return (ord[i] < ord[j]) ? ord[i] < low[j] : ord[j] < low[i];
    }
    const vector<int>& getComp() const
    {
        return comp;
    }

private:
    void bridge_dfs(const CostGraph& g_, const int s, const int par = -1)
    {
        ord[s] = num;
        low[s] = num;
        num++;
        for (const auto& e : g_.edge[s]) {
            const int to = e.to;
            if (to == par) {
                continue;
            }
            if (ord[to] >= 0) {
                low[s] = min(low[s], ord[to]);
            } else {
                bridge_dfs(g_, to, s);
                low[s] = min(low[s], low[to]);
            }
            if (isBridge(s, to)) {
                bridge.push_back(e);
            }
        }
    }

    void comp_dfs(const CostGraph& g_, const int s, const int c)
    {
        comp[s] = c;
        for (const auto& e : g_.edge[s]) {
            const int to = e.to;
            if ((comp[to] == -1) and (not isBridge(s, to))) {
                comp_dfs(g_, to, c);
            }
        }
    }
    int num;
    int comp_num;
    const int size;
    vector<CostGraph::Edge> bridge;
    vector<int> ord;
    vector<int> low;
    vector<int> comp;
};

int main()
{
    int n, m;
    cin >> n >> m;

    CostGraph g(n);
    using pii = pair<int, int>;
    map<pii, ll> cost;
    vector<pii> edge(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        a--, b--;
        g.addEdge(a, b, c);
        edge[i] = make_pair(a, b);
        cost[edge[i]] = c;
    }
    vector<ll> ds(n, INF<ll>);
    Dijkstra(g, 0, ds);
    vector<ll> dt(n, INF<ll>);
    ReverseDijkstra(g, 1, dt);
    show(ds);
    show(dt);
    const ll D = ds[1];
    CostGraph undg(n);
    for (int i = 0; i < m; i++) {
        const pii e = edge[i];
        const int u = e.first;
        const int v = e.second;
        const ll c = cost[e];
        if (ds[u] + c == ds[v]) {
            undg.addEdge(u, v, 1);
            undg.addEdge(v, u, 1);
        }
    }

    for (int i = 0; i < n; i++) {
        for (const auto& e : undg.edge[i]) {
            cerr << e.from << "->" << e.to << endl;
        }
    }

    BiconnectedComponent bic(undg);
    for (int i = 0; i < m; i++) {
        const pii e = edge[i];
        const int u = e.first;
        const int v = e.second;
        const ll c = cost[e];
        if (ds[v] + c + dt[u] < D) {
            cout << "HAPPY" << endl;
        } else {
            if (bic.isBridge(u, v)) {
                cout << "SAD" << endl;
            } else {
                cout << "SOSO" << endl;
            }
        }
    }
    return 0;
}

Compiler output:
a.cc:13:19: error: 'numeric_limits' was not declared in this scope
   13 | constexpr T INF = numeric_limits<T>::max() / 16;
      |                   ^~~~~~~~~~~~~~
a.cc:13:35: error: expected primary-expression before '>' token
   13 | constexpr T INF = numeric_limits<T>::max() / 16;
      |                                   ^
a.cc:13:41: error: no matching function for call to 'max()'
   13 | constexpr T INF = numeric_limits<T>::max() / 16;
      |                                    ~~~~~^~
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   candidate expects 2 arguments, 0 provided
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 0 provided