{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003cbr\u003e我的名字是胡八一,我正在西藏探险一个古墓。这个墓室包括N个房间(编号从1到N),它们之间由一些道路连接(通过每条道路都需要花费一些时间)。任意两个房间之间都有且只有一条路径,每个房间都包含一些宝藏。现在我位于第一个房间,出口位于第N个房间。\u003cbr\u003e突然间,警报响起!墓室将在T分钟内倒塌,我必须在T分钟内到达出口房间。人为财死,鸟为食亡!虽然这是危及生命的时刻,但我还是想尽可能多地带走宝藏。现在我想知道在T分钟内我能带走的最大宝藏数量。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"有多个测试用例。\u003cbr\u003e第一行包含两个整数N和T。(1 \u003c\u003d n \u003c\u003d 100, 0 \u003c\u003d T \u003c\u003d 500)\u003cbr\u003e接下来的N - 1行,每行包含三个整数a、b和t,表示a和b之间有一条耗时t分钟的道路。(1\u003c\u003da\u003c\u003dn, 1\u003c\u003db\u003c\u003dn, a!\u003db, 0 \u003c\u003d t \u003c\u003d 100)\u003cbr\u003e最后一行包含N个整数,其中Ai表示第i个房间中的宝藏数量。(0 \u003c\u003d Ai \u003c\u003d 100)\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一个整数,表示我在T分钟内能带走的最大宝藏数量;如果我无法走出墓室,请输出\"人为财死,鸟为食亡!\"。\u003cbr\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 10\r\n1 2 2 \r\n2 3 2\r\n2 5 3\r\n3 4 3\r\n1 2 3 4 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}