33672번 - Underspecified Ultrametrics 다국어

문제

Given a set of points $X$ with distances $d(u,v)$ between any $u,v \in X,ドル we say that $(X,d)$ is an ultrametric if the following properties are satisfied:

• $d(u,v)≥0$ for any two points $u,ドル $v$ with $d(u,v)=0$ if and only if $u=v$
• $d(u,v)=d(v,u)$ for any two points $u,ドル $v$
• $d(u,v)≤\max\{d(u,w),d(w,v)\}$ for any three points $u,ドル $v,ドル $w$

That is, distances in an ultrametric satisfy a slightly stronger property than the usual triangle inequality $d(u,v)≤d(u,w)+d(w,v)$.

You have measured distances between some pair of points from some set $X$ and start to wonder if you might be looking at an ultrametric. Write a program to help you determine if this is the case!

입력

The first line of input contains two integers $N$ (3ドル≤N≤100,000円$) and $M$ (0ドル≤M≤400,000円$) where $N$ is the number of points in the set $X$ and $M$ is the number of distances you have determined so far. The points are numbered from 0ドル$ to $N-1$.

Then $M$ lines follow, each containing three integers $u,ドル $v,ドル $l$ (0ドル≤u<v<N$ and 1ドル≤l≤10^9$) where $u,ドル $v$ are two points in $X$ and $l$ is the distance $d(u,v)$ you have determined between these points. No pair of points will have their distance specified on more than on line.

출력

Output possibly ultrametric if there is an ultrametric $(X,d')$ where the distances satisfy $d'(u,v)=d(u,v)$ for any $u,v \in X$ such that one of the $M$ given distances you have already determined is for the pair $(u,v)$. Otherwise, output the message not ultrametric.

제한

힌트