{"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高玩小Q不仅喜欢玩寻宝游戏,还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有$n$个城镇,编号依次为$1$到$n$。\u003cbr\u003e\u003cbr\u003e这些城镇之间有$m$条单向道路,第$i$ 条单项道路包含四个参数$u_i,v_i,a_i,b_i$,表示一条从$u_i$号城镇出发,在$v_i$号城镇结束的单向道路,因为是单向道路,这不意味着小Q可以从$v_i$沿着该道路走到$u_i$。小Q的初始等级$level$为$1$,每当试图经过一条道路时,需要支付$cost\u003d\\log_2\\frac{level+a_i}{level}$点积分,并且经过该道路后,小Q的等级会提升$a_i$级,到达$level+a_i$级。但是每条道路都会在一定意义上歧视低消费玩家,准确地说,如果该次所需积分$cost\u0026lt;b_i$,那么小Q不能经过该次道路,也不能提升相应的等级。\u003cbr\u003e\u003cbr\u003e注意:本游戏中等级为正整数,但是积分可以是任意实数。\u003cbr\u003e\u003cbr\u003e小Q位于$1$号城镇,等级为$1$,现在为了做任务要到$n$号城镇去。这将会是一次奢侈的旅行,请写一个程序帮助小Q找到需要支付的总积分最少的一条路线,或判断这是不可能的。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含一个正整数$T(1\\leq T\\leq 30)$,表示测试数据的组数。\u003cbr\u003e\u003cbr\u003e每组数据第一行包含两个整数$n,m(2\\leq n\\leq 100000,1\\leq m\\leq 200000)$,表示城镇数和道路数。\u003cbr\u003e\u003cbr\u003e接下来$m$行,每行四个整数$u_i,v_i,a_i,b_i(1\\leq u_i,v_i\\leq n,u_i\\neq v_i,0\\leq a_i\\leq 10^9,0\\leq b_i\\leq 60)$,分别表示每条单向道路。"}},{"title":"Output","value":{"format":"HTML","content":"对于每组数据,输出一行一个整数,即最少所需的总积分的整数部分,如:$4.9999$输出$4$,$1.0$输出$1$。若不存在合法路线请输出$-1$。"}},{"title":"Sample","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\u003e1\r\n3 3\r\n1 2 3 2\r\n2 3 1 6\r\n1 3 5 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}