题目描述

给出一个 $n$ 个点 $m$ 条边的带权无向图，边上的权值代表两点之间的距离。每个点上有两个值，$t,c$，表示从这个点最远走到走 $t$，且不能在半路停下来，花费是 $c$。

现在告诉你起点终点，问最少花费。$n, m \le 1000$，边权 $\le 10^9$。

输入格式

第一行两个整数 $n, m$。

第二行两个整数 $a, b$，表示起点和终点。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示点 $u,v$ 之间存在一条边权为 $w$ 的边。

接下来 $n$ 行，每行两个整数 $t,c$，依次表示点 $1 \sim n$ 的两个值。

输出格式

一个整数表示答案。若无解则输出 -1。

4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7

9