{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003eProblem F\n \n \u003c/h2\u003e\n\n\u003cp\u003e\n Alyssa is a college student, living in New Tsukuba City. All the streets in the city are one-way. A new social experiment starting tomorrow is on alternative traffic regulation reversing the one-way directions of street sections. Reversals will be on one single street section between two adjacent intersections for each day; the directions of all the other sections will not change, and the reversal will be canceled on the next day.\n\u003c/p\u003e\n\n\u003cp\u003e\nAlyssa orders a piece of pizza everyday from the same pizzeria. The pizza is delivered along the shortest route from the intersection with the pizzeria to the intersection with Alyssa\u0027s house.\n\u003c/p\u003e\n\n\u003cp\u003e\n Altering the traffic regulation may change the shortest route. Please tell Alyssa how the social experiment will affect the pizza delivery route.\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\n The input consists of a single test case in the following format.\n\u003c/p\u003e\n\n\u003cpre\u003e$n$ $m$\n$a_1$ $b_1$ $c_1$\n...\n$a_m$ $b_m$ $c_m$\n\u003c/pre\u003e\n\n\u003cp\u003e\n The first line contains two integers, $n$, the number of intersections, and $m$, the number of street sections in New Tsukuba City ($2 \\leq n \\leq 100 000, 1 \\leq m \\leq 100 000$). The intersections are numbered $1$ through $n$ and the street sections are numbered $1$ through $m$.\n\u003c/p\u003e\n\n\u003cp\u003e\n The following $m$ lines contain the information about the street sections, each with three integers $a_i$, $b_i$, and $c_i$ ($1 \\leq a_i n, 1 \\leq b_i \\leq n, a_i \\ne b_i, 1 \\leq c_i \\leq 100 000$). They mean that the street section numbered $i$ connects two intersections with the one-way direction from $a_i$ to $b_i$, which will be reversed on the $i$-th day. The street section has the length of $c_i$. Note that there may be more than one street section connecting the same pair of intersections.\n\u003c/p\u003e\n\n\u003cp\u003e\n The pizzeria is on the intersection 1 and Alyssa\u0027s house is on the intersection 2. It is guaranteed that at least one route exists from the pizzeria to Alyssa\u0027s before the social experiment starts.\n\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\n The output should contain $m$ lines. The $i$-th line should be\n\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e \u003cspan\u003eHAPPY\u003c/span\u003e if the shortest route on the $i$-th day will become shorter,\u003c/li\u003e\n\u003cli\u003e \u003cspan\u003eSOSO\u003c/span\u003e if the length of the shortest route on the $i$-th day will not change, and\u003c/li\u003e\n\u003cli\u003e \u003cspan\u003eSAD\u003c/span\u003e if the shortest route on the $i$-th day will be longer or if there will be no route from the pizzeria to Alyssa\u0027s house.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\n Alyssa doesn\u0027t mind whether the delivery bike can go back to the pizzeria or not.\n\u003c/p\u003e\n\n\n\u003ch3\u003eSample Input 1\u003c/h3\u003e\n\u003cpre\u003e4 5\n1 3 5\n3 4 6\n4 2 7\n2 1 18\n2 3 12\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 1\u003c/h3\u003e\n\u003cpre\u003eSAD\nSAD\nSAD\nSOSO\nHAPPY\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Input 2\u003c/h3\u003e\n\u003cpre\u003e7 5\n1 3 2\n1 6 3\n4 2 4\n6 2 5\n7 5 6\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 2\u003c/h3\u003e\n\u003cpre\u003eSOSO\nSAD\nSOSO\nSAD\nSOSO\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Input 3\u003c/h3\u003e\n\u003cpre\u003e10 14\n1 7 9\n1 8 3\n2 8 4\n2 6 11\n3 7 8\n3 4 4\n3 2 1\n3 2 7\n4 8 4\n5 6 11\n5 8 12\n6 10 6\n7 10 8\n8 3 6\n\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 3\u003c/h3\u003e\n\u003cpre\u003eSOSO\nSAD\nHAPPY\nSOSO\nSOSO\nSOSO\nSAD\nSOSO\nSOSO\nSOSO\nSOSO\nSOSO\nSOSO\nSAD\n\u003c/pre\u003e"}}]}