pizza_verTrung

#include<bits/stdc++.h>
#define int             long long
using namespace std;

void Read(int &val) {
    val = 0; char c;
    do { c = getchar(); } while (!isdigit(c));
    while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
}
void Write(int type) {
    if (type == -1) {
        putchar('S'); putchar('A'); putchar('D');
    }
    else if (type == 1) {
        putchar('H'); putchar('A'); putchar('P'); putchar('P'); putchar('Y');
    }
    else {
        putchar('S'); putchar('O'); putchar('S'); putchar('O');
    }
    putchar('\n');
}

struct data {
    int u, v, w;
    data() {}; data(int u, int v, int w) : u(u), v(v), w(w) {};
};
typedef pair<int, int> ii;

const int N = 2e5 + 4, LOG = 20, oo = 1e16;
int n, m;
data Edge[N];
vector<ii> adj[N];

int d[3][N];
priority_queue<ii, vector<ii>, greater<ii> > pq;

int hei[N], vis[N], par[N][LOG+4], mom[N];
vector<int> Prev[N], Next[N];

map<ii, bool> Map;
map<ii, int> cost, Count;

void Dijkstra(int id, int Start) {
    for (int i = 1; i <= n; ++i) d[id][i] = oo; d[id][Start] = 0;
    pq.push(ii(0, Start));
    while (pq.size()) {
        int u = pq.top().second, du = pq.top().first; pq.pop();
        if (du != d[id][u]) continue;
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].second, uv = adj[u][i].first;
            if (d[id][v] > du + uv) {
                d[id][v] = du + uv; pq.push(ii(d[id][v], v));
                if (id == 1) { Prev[v].clear(); Prev[v].push_back(u); }
            }
            else if (d[id][v] == du + uv && id == 1) Prev[v].push_back(u);
        }
    }
}

int LCA(int u, int v) {
    if (hei[u] < hei[v]) swap(u, v);
    for (int i = LOG; i >= 0; --i)
        if (hei[u] - (1<<i) >= hei[v]) u = par[u][i];
    if (u == v) return u;
    for (int i = LOG; i >= 0; --i)
        if (par[u][i] != 0 && par[v][i] != 0 && par[u][i] != par[v][i]) {
            u = par[u][i]; v = par[v][i];
        }
    return par[u][0];
}

void DFS(int u) {
    vis[u]++;
    if (vis[u] == Prev[u].size()) {
        int dad = 0;
        for (int i = 0; i < Prev[u].size(); ++i) {
            int v = Prev[u][i];
            dad = (i == 0) ? v : LCA(dad, v);
        }
        par[u][0] = dad; hei[u] = hei[dad] + 1; mom[u] = dad;
        for (int i = 1; i <= LOG; ++i) par[u][i] = par[par[u][i-1]][i-1];

        for (int v : Next[u]) DFS(v);
    }
}

void BuildDomTree() {
    for (int v = 1; v <= n; ++v) {
        for (int u : Prev[v]) Next[u].push_back(v);
    }
    Prev[1].push_back(0);
    DFS(1);
}

void AnswerQuery() {
    int u = 2;
    while (u != 1) { Map[ii(mom[u], u)] = true; u = mom[u]; }

    for (int i = m; i <= m; ++i) {
        int u = Edge[i].u, v = Edge[i].v;
        bool ok = (d[1][u] + d[2][v] + Edge[i].w == d[1][2]);
        if (Map[ii(u, v)] && Edge[i].w > cost[ii(u, v)] && ok) {
            Write(0); continue;
        }
        if (Map[ii(u, v)] && Edge[i].w == cost[ii(u, v)] && Count[ii(u, v)] >= 2 && ok) {
            Write(0); continue;
        }
        if (Map[ii(u, v)] && ok) {
            Write(-1); continue;
        }
        if (d[1][v] + d[2][u] + Edge[i].w < d[1][2]) Write(1);
        else Write(0);
    }
}

void sol() {
    for (int i = 1; i <= m; ++i) {
        int u = Edge[i].u, v = Edge[i].v, w = Edge[i].w;
        adj[u].push_back(ii(w, v));
    }
    Dijkstra(1, 1);

    for (int i = 1; i <= n; ++i) adj[i].clear();
    for (int i = 1; i <= m; ++i) {
        int u = Edge[i].u, v = Edge[i].v, w = Edge[i].w;
        adj[v].push_back(ii(w, u));
    }
    Dijkstra(2, 2);
//
    BuildDomTree();
    AnswerQuery();
}

main() {
    freopen("pizza.in", "r", stdin);
    freopen("pizza.out", "w", stdout);

    Read(n); Read(m);
    int u, v, w;
    for (int i = 1; i <= m; ++i) {
        Read(u); Read(v); Read(w);
        Edge[i] = data(u, v, w);
            int tmp = cost[ii(u, v)];
            if (tmp == 0) cost[ii(u, v)] = w, Count[ii(u, v)] = 1;
            else {
                if (tmp > w) cost[ii(u, v)] = w, Count[ii(u, v)] = 1;
                else if (tmp == w) Count[ii(u, v)]++;
            }
    }

    sol();

    return 0;
}