道路权值审计

难度：T2

【知识点：复杂度与算法审计】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

检查有向图是否满足全部边权非负这一条件。这里只做条件检查，不计算路径，也不把某条负边不可达作为例外。

输入格式

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$；$m$ 为随后给出的带权边条数。每条带权边独占一行，依次为 $u,v,w$，表示从 $u$ 到 $v$ 的边及权值 $w$；无向边可双向通行，有向边只能从 $u$ 到 $v$ 通行。

输入$n$、$m$和$m$条有向边$u$、$v$、$w$。这里只审核Dijkstra的全图非负权前提，不求距离。

输出格式

全部边权非负输出SUPPORTED，有任一负边输出UNSUPPORTED。

数据范围

$1\le n\le 100000$，$0\le m\le 200000$，$|w|\le 10^9$，编号在$1$..$n$。

样例输入

1 0

样例输出

SUPPORTED

样例输入 2

3 2
1 2 1
2 3 -1

样例输出 2

UNSUPPORTED

样例说明 2

存在边权为 $-1$ 的边，不满足全部边权非负的条件。