Migrated from Lutece 2560 土豆的技能树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

wyh 队长说过：「飞土豆的技能树需要添枝加叶了。」，wyh 队长还说过：「基础不牢，地动山摇。」

总之，土豆为了队伍开始磨练自己的技能了，技能树虽然是一棵树，但是它其实是一张图，图上有许多的节点代表大的知识专题，比如数据结构、动态规划、图论等，两个节点之间可能有一条带权有向边，代表某个知识点，权值代表土豆对这个知识点的掌握力，比如连接数据结构和图论的边可能代表树链剖分。土豆是一位蠢笨的选手，他虽然有无穷的技能点可以加到每个知识专题（节点）上，但是这并不能让这个专题的所有知识点变强。反之，每个加到该专题的技能点会使任何离开这个专题的知识点边权加 $1$，也会使所有指向这个专题的知识点边权减 $1$。土豆想成为一个全能的选手，于是他问你他能变得多全能，你能帮他找到一个最大的正整数 $r$，使得加完技能点后所有知识点的掌握力都大于等于 $r$ 吗？

Input

多组输入，每组输入第一行包含两个整数 $n,m$，代表专题的个数和知识点的个数。

接下来的 $m$ 行，每行三个整数 $u,v,w$，表示每个知识点从哪个专题离开，指向哪个专题，土豆对这个知识点的掌握力。

Output

如果存在最大的符合要求的正整数 $r$，输出它。如果 $r$ 可以为无穷大，输出 best potato ever，如果没有这样的正整数，输出 budagun。

Samples

3 2
2 3 -10
1 2 10
2 1
2 3 -10
3 3
1 2 -10
2 3 -10
3 1 -10
2 1
1 1 1

best potato ever
best potato ever
budagun
1

Constraints

单组数据保证： $n\le600$ $m\le3000$ $|w|\le10000$ 所有数据保证： $\sum{n}\le12000$ $\sum{m}\le6 \cdot 10^4$ 题中所给的图可能存在自环和重边 题目中点的序号可能大于点数，但保证小于单组最大点数

Resources

2021 UESTC ICPC Training for Graph