奢侈的旅行

高玩小Q不仅喜欢玩寻宝游戏，还喜欢一款升级养成类游戏。在这个游戏的世界地图中一共有$n$个城镇，编号依次为$1$到$n$。

这些城镇之间有$m$条单向道路，第$i$ 条单项道路包含四个参数$u_i,v_i,a_i,b_i$，表示一条从$u_i$号城镇出发，在$v_i$号城镇结束的单向道路，因为是单向道路，这不意味着小Q可以从$v_i$沿着该道路走到$u_i$。小Q的初始等级$level$为$1$，每当试图经过一条道路时，需要支付$cost=\log_2\frac{level+a_i}{level}$点积分，并且经过该道路后，小Q的等级会提升$a_i$级，到达$level+a_i$级。但是每条道路都会在一定意义上歧视低消费玩家，准确地说，如果该次所需积分$cost<b_i$，那么小Q不能经过该次道路，也不能提升相应的等级。

注意：本游戏中等级为正整数，但是积分可以是任意实数。

小Q位于$1$号城镇，等级为$1$，现在为了做任务要到$n$号城镇去。这将会是一次奢侈的旅行，请写一个程序帮助小Q找到需要支付的总积分最少的一条路线，或判断这是不可能的。

第一行包含一个正整数$T(1\leq T\leq 30)$，表示测试数据的组数。

每组数据第一行包含两个整数$n,m(2\leq n\leq 100000,1\leq m\leq 200000)$，表示城镇数和道路数。

接下来$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)$，分别表示每条单向道路。

对于每组数据，输出一行一个整数，即最少所需的总积分的整数部分，如：$4.9999$输出$4$，$1.0$输出$1$。若不存在合法路线请输出$-1$。

1
3 3
1 2 3 2
2 3 1 6
1 3 5 0

2

"字节跳动杯"2018中国大学生程序设计竞赛-女生专场