Sub-prime

One cause of the recent economic crisis is that banks lent money to people who could not repay it, then bundled those loans into debentures and sold them on to other banks. Once the borrowers stopped paying, the whole structure collapsed.

The crisis reached Nlogonia. Prime minister Man Dashuva asked the chairman of the Central Bank for a way out, and the chairman proposed this: if every bank can clear all the debentures it issued using only its own monetary reserve and the debentures owed to it, no bailout is needed.

The number of banks and debentures makes this impossible to check by hand. Given the banks and the debentures they issued, decide whether all debentures can be cleared without a bailout from the Central Bank of Nlogonia.

All debentures settle at the same time. After settlement, bank $i$ holds its reserve $R_i$ minus the total value of the debentures it issued, plus the total value of the debentures for which it is the creditor. If that amount is negative for at least one bank, a bailout is necessary. If every bank ends at $0$ or more, no bailout is necessary.

The input holds several test cases. The first line of each test case has two integers $B$ and $N$ separated by a space, the number of banks ($1 \le B \le 20$) and the number of debentures the banks issued ($1 \le N \le 20$). Banks are numbered from $1$ to $B$. The second line has $B$ integers $R_i$ separated by spaces, where $R_i$ is the monetary reserve of bank $i$ ($0 \le R_i \le 10^4$). Each of the next $N$ lines has three integers separated by spaces: $D$, the debtor bank ($1 \le D \le B$), $C$, the creditor bank ($1 \le C \le B$ and $D \ne C$), and $V$, the debenture value ($1 \le V \le 10^4$).

Several debentures may connect the same pair of banks.

The end of the input is a line holding only two zeros separated by a space. Do not process that line.

For each test case print one line holding a single character: S if all debentures can be cleared without a bailout from the Central Bank of Nlogonia, or N if a bailout is necessary.