Le milliardaire Christian a découvert aujourd'hui l'algorithme de Dijkstra avec les potentiels de Johnson. Il l'a tellement apprécié qu'il a décidé d'ajouter des potentiels à tous ses graphes préférés. Christian a des goûts très particuliers : il ne conserve que des graphes orientés pondérés dans sa pièce secrète.
Rappelons comment fonctionnent les potentiels. Chaque sommet $v$ reçoit un potentiel : un réel $\varphi(v)$. S'il existait un arc de $u$ vers $v$ de poids initial $w$, son nouveau poids sera $w'=w-\varphi(v)+\varphi(u)$.
La force d'un graphe est définie comme le minimum des poids de ses arcs. Christian ne veut pas de graphes faibles dans sa pièce ; il souhaite donc choisir les potentiels de façon à maximiser la force du graphe. Aidez-le.
Entrée
La première ligne contient deux entiers $n$ ($2\le n\le1000$) et $m$ ($1\le m\le100\,000$), les nombres de sommets et d'arcs du graphe préféré de Christian. Chacune des $m$ lignes suivantes contient trois entiers $u_i,v_i,w_i$ décrivant un arc : son origine, sa destination et son poids, respectivement ($1\le u_i,v_i\le n$, $|w_i|\le10^6$).
Sortie
La première ligne doit contenir la force maximale du graphe. S'il est possible de rendre la réponse infiniment grande, affichez à la place la chaîne « +inf ».
Si la réponse est finie, la deuxième ligne doit contenir $n$ réels : les potentiels des sommets. La valeur absolue de chacun ne doit pas dépasser $10^{10}$. Votre réponse ne doit différer ni de la réponse correcte, ni de celle calculée à partir de vos potentiels, de plus de $10^{-5}$.
Exemples
Entrée 1
3 3 1 2 1 2 3 1 3 1 1
Sortie 1
1.0 0.0 0.0 0.0
Entrée 2
2 1 1 2 1
Sortie 2
+inf