#8 「 小迟修马路 」

统计

小迟生活的城市是一棵树(树指的是一个含有$n$个节点以及$n-1$条边的无向连通图),节点编号从$1$到$n$,每条边拥有一个权值value,表示通过这条边的时候你需要交纳的金钱(注意,有可能这个值为负数,也就是说你经过这条边的时候你可以赚钱)。

小迟是一个杰出的马路工,他居住在节点$s$,他能够选择任意一个节点$m$,并将从节点$s$到节点$m$的简单路径(简单路径指的是不经过同一个节点两次)上的所有边的权值都修改为$0$。

现在小迟获得$q$个请求,每个请求都是以$a\ b$的形式给出,表示小迟的好朋友小早希望从节点$a$走简单路径到节点$b$,小迟希望能最小化小早需要缴纳的钱。

需要注意的是,小迟获得的这$q$个请求是相互独立的,也就是说您只需要对于每一个请求,决定小迟的一个修路方案,使得小早需要缴纳的钱尽可能的少。

输入格式

第一行三个正整数为$n$,$q$,$s$。

接下来$n-1$行,每行三个整数$x\ y\ z$,表示有一条边$(x,y)$,value为$z$。

接下来$q$行,每行两个正整数$a\ b$,表示请求。

输出格式

$q$行,每行一个整数,表示需要缴纳的最少的钱。

样例数据

input

3 2 1
1 2 1
2 3 1
1 2
1 3

output

0
0

样例解释

对于第一次询问$1\ 2$,小迟可以修从$1$到$2$的路,从而使得小早不需要缴纳金钱;

对于第二次询问$1\ 3$,小迟可以修从$1$到$3$的路,从而使得小早不需要缴纳金钱。

数据规模与约定

$1 \le n,q \le 200000, 1 \le x,y \le n,|z| \le 1000$。

时间限制:3s

空间限制:512MB

Author: Nineteen