{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003e问题 F\u003c/h2\u003e\n\n\u003cp\u003e\n Alyssa是一名大学生,住在New Tsukuba City。城市中的所有街道都是单向的。从明天开始的一个新社会实验是交通规则的替代性调整,即颠倒街道段的单向方向。每天只会在两个相邻交叉口之间的一条街道段上进行颠倒;其他所有街道段的方向不会改变,并且颠倒将在第二天取消。\n\u003c/p\u003e\n\n\u003cp\u003e\nAlyssa每天都从同一家比萨店订购一份比萨。比萨是沿着从比萨店到Alyssa家的交叉口的最短路径送达的。\n\u003c/p\u003e\n\n\u003cp\u003e\n 调整交通规则可能会改变最短路径。请告诉Alyssa社会实验将如何影响比萨送货路线。\n\u003c/p\u003e\n\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e\n 输入包含一个单独的测试用例,格式如下。\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 第一行包含两个整数,$n$,表示New Tsukuba City中的交叉口数和街道段数($2 \\leq n \\leq 100 000, 1 \\leq m \\leq 100 000$)。交叉口编号从$1$到$n$,街道段编号从$1$到$m$。\n\u003c/p\u003e\n\n\u003cp\u003e\n 接下来的$m$行包含有关街道段的信息,每行包含三个整数$a_i$,$b_i$和$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$)。它们表示街道段编号为$i$,连接两个交叉口,单向方向从$a_i$到$b_i$,将在第$i$天颠倒。该街道段的长度为$c_i$。请注意,可能有多个街道段连接相同的交叉口对。\n\u003c/p\u003e\n\n\u003cp\u003e\n 比萨店位于交叉口1,Alyssa的家位于交叉口2。保证在社会实验开始之前,从比萨店到Alyssa家至少存在一条路径。\n\u003c/p\u003e\n\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e\n 输出应包含$m$行。第$i$行应为\n\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e 如果第$i$天的最短路径变短,则为\u003cspan\u003eHAPPY\u003c/span\u003e,\u003c/li\u003e\n\u003cli\u003e 如果第$i$天的最短路径长度不变,则为\u003cspan\u003eSOSO\u003c/span\u003e,\u003c/li\u003e\n\u003cli\u003e 如果第$i$天的最短路径变长或者从比萨店到Alyssa家没有路径,则为\u003cspan\u003eSAD\u003c/span\u003e。\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\n Alyssa不在乎送货车是否能返回比萨店。\n\u003c/p\u003e\n\n\u003ch3\u003e样例输入 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\u003e样例输出 1\u003c/h3\u003e\n\u003cpre\u003eSAD\nSAD\nSAD\nSOSO\nHAPPY\n\u003c/pre\u003e\n\n\u003ch3\u003e样例输入 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\u003e样例输出 2\u003c/h3\u003e\n\u003cpre\u003eSOSO\nSAD\nSOSO\nSAD\nSOSO\n\u003c/pre\u003e\n\n\u003ch3\u003e样例输入 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\u003e样例输出 3\u003c/h3\u003e\n\u003cpre\u003eSOSO\nSAD\nHAPPY\nSOSO\nSOSO\nSOSO\nSAD\nSOSO\nSOSO\nSOSO\nSOSO\nSOSO\nSOSO\nSAD\n\u003c/pre\u003e"}}]}