亿万富翁 Christian 今天学到了带 Johnson 势函数的 Dijkstra 算法。他非常喜欢这个算法，决定给自己所有心爱的图都加上势。Christian 的品味十分独特——他的密室里只收藏有向带权图。

让我们回顾一下势的作用。每个顶点 $v$ 都被赋予一个势，即实数 $\varphi(v)$。如果原来有一条从 $u$ 到 $v$、权值为 $w$ 的边，那么它的新权值为 $w'=w-\varphi(v)+\varphi(u)$。

一个图的强度定义为所有边权的最小值。Christian 不希望自己的房间里出现弱小的图，因此他想选择适当的势，使图的强度最大。请帮助他。

输入格式

第一行包含两个整数 $n$（$2\le n\le1000$）和 $m$（$1\le m\le100\,000$），分别表示 Christian 心爱的图的顶点数和边数。接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$，依次描述一条边的起点、终点和权值（$1\le u_i,v_i\le n$，$|w_i|\le10^6$）。

输出格式

第一行必须输出图的最大强度。如果可以使答案无限大，则改为输出字符串“+inf”。

如果答案有限，第二行必须输出 $n$ 个实数，表示各顶点的势。每个数的绝对值都不能超过 $10^{10}$。你输出的答案与正确答案的差，以及与你输出的势所计算出的答案的差，都不能超过 $10^{-5}$。

样例

输入格式 1

3 3
1 2 1
2 3 1
3 1 1

输出格式 1

1.0
0.0 0.0 0.0

输入格式 2

2 1
1 2 1

输出格式 2

+inf