题目描述

动态配送任务要求机器人既完成载荷转移，又不能把自己困在无法返航的位置。具身智能部把电量、载荷和风险共同放进状态里，训练你做带返航保证的重规划。

你需要在扩展状态图上搜索最优路径，状态中包含当前位置、载荷阶段、电量余量和风险约束。每一步转移都必须满足题面给定的预算和返航条件。

请小心处理风险预算、电量等号、阶段切换和不可达输出；路径比较必须按题面顺序稳定执行。

输入格式

第一行输入图规模：

V E

第二行输入：

start pickup drop safe

第三行输入：

init_energy load max_risk reserve

接下来 E 行无向边：

u v dist energy_empty energy_load risk blocked

输出格式

若能完成取货、投放并到达安全点，输出：

SUCCESS 1 path... dist energy_used risk 0 safe

若不存在满足返航和风险约束的路径，输出 SAFE_STOP。

判定规则

状态包含当前位置、阶段、电量和累计风险。阶段 0 表示尚未取货，到达 pickup 后进入阶段 1；阶段 1 表示载货，到达 drop 后进入阶段 2；阶段 2 表示返航，到达 safe 后成功。

禁用边 blocked = 1 不可走。空载能耗为 energy_empty，载货能耗为 energy_empty + load * energy_load。任一步后电量必须 >= reserve，累计风险必须 <= max_risk。用最小距离优先搜索；同距离时风险和路径字典序稳定决定输出。

数据范围与测试提示

• 所有编号均按题面说明使用 1-based；字符串枚举按输入原样比较。
• 正式测试会覆盖安全停止、无可行分支、阈值等号、并列比较和恢复失败等边界情况。
• 输出只包含题目要求的字段，不要输出调试信息。

样例

输入样例 1

4 3
1 2 3 4
20 1 5 1
1 2 2 2 1 1 0
2 3 2 2 1 1 0
3 4 2 2 1 1 0

输出样例 1

SUCCESS 1 1 2 3 4 6 7 3 0 4

输入样例 2

4 3
1 2 3 4
20 1 5 1
1 2 2 2 1 1 1
2 3 2 2 1 1 0
3 4 2 2 1 1 0

输出样例 2

SAFE_STOP