奢侈的旅行
题目描述:
高玩小 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 50000, 1\leq m\leq 100000)\)，表示城镇数和道路数。
接下来 \(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
提示:
请使用复杂度正确的算法。
请注意浮点数误差。
空间限制: 256MB
来源: hdu 6290