题号：NC22615
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
给出一个城市的交通网络，该城市共有n个地点。共有n-1条有向道路，1号节点为关键节点。保证从关键节点出发可以到达任何一个节点。而且市长为了奖励那些离开关键城市，来减轻关键城市压力的人。每个沿着有向道路i的方向走的人都会获得
的收益。但是如果你足够有钱，你也可以强行逆行。但是这样会花费
的罚款。对于一条道路如果你已经得到过一次奖励那么不会再得到奖励。同样的，如果你已经在这条道路上被罚过一次款了，那么你不会在被罚第二次。
现在你要从你工作的S地点到你的家T地点。因为今年没挣到钱，所以你希望在回家途中可以得到尽可能多的money。现在你需要告诉你父母你今年挣到了多少钱。所以你需要多次回答从S到T你总共可以赚到多少￥。
由于种种原因，你要保证可以到达的情况下尽可能的离关键城市远。
现在你要从你工作的S地点到你的家T地点。因为今年没挣到钱，所以你希望在回家途中可以得到尽可能多的money。现在你需要告诉你父母你今年挣到了多少钱。所以你需要多次回答从S到T你总共可以赚到多少￥。
由于种种原因，你要保证可以到达的情况下尽可能的离关键城市远。
如果你没有看懂上面的题意，请看简化版题意:
给出一棵以1号节点为根的树，对于第i条边，从父亲走向儿子会得到
的收益，从儿子走向父亲会付出
的代价。每次询问从S到T最多的收益是多少。
注意：在保证可以到达的情况下，要尽可能使路径上距离1号点最近的点与1号点之间的距离最远！！！而且此路径不一定是简单路径。
答案可能会是负收益
输入描述:
第一行两个个正整数n,Q,表示一共有n个节点总共有Q次询问。
下面n-1行每行4个整数u,v,w,c，表示u,v之间有一条边(注意uv并不代表方向)，顺行会得到w的收益，逆行会被罚款c。
然后Q行，每行两个正整数S，T。询问从S到T最多收益是多少。
输出描述:
输出共Q行，第i行表示第i次询问的答案。
