背景

译自 Natjecanje timova studenata informatičara hrvatskih sveučilišta H.

题目描述

给定两张 $n$ 个点的无向连通图 $G_1(V_1,E_1),G_2(V_2,E_2)$。边有边权。

初始时童子军们在起点 $s$，他们要行军到终点 $t$。

他们的行动会遵循以下规则：

令童子军当前在节点 $x$，

• 第 $1,3,5,\cdots$ 次移动，他们会选择一条边 $(x,y,w)\in E_1$，然后移动到 $y$。
  • 令 $\operatorname{dist}_1(x,y)$ 表示 $G_1$ 中 $x,y$ 之间的最短路长度。$\operatorname{dist}_1(x,t)\textcolor{red}{\gt}\operatorname{dist}_1(y,t)$ 必须满足。
• 第 $2,4,6,\cdots$ 次移动，他们会选择一条边 $(x,y,w)\in E_2$，然后移动到 $y$。
  • 令 $\operatorname{dist}_2(x,y)$ 表示 $G_2$ 中 $x,y$ 之间的最短路长度。$\operatorname{dist}_2(x,t)\textcolor{red}{\gt}\operatorname{dist}_2(y,t)$ 必须满足。

你需要求出，在满足上述条件的情况下，从起点到终点经过边的边权和的最大值。

特别地，最大值可以为无穷大，即他们可以永远走不到终点。在符合条件的情况下，可以一直拖着不走到终点。

输入格式

第一行，三个正整数 $n,s,t$。

第二行，一个正整数 $m_1$，表示 $G_1$ 的边数 $|E_1|$。

接下来 $m_1$ 行，每行三个正整数 $u,v,w$，表示 $(u,v,w)\in E_1$。

第 $(m_1+3)$ 行，一个正整数 $m_2$，表示 $G_2$ 的边数 $|E_2|$。

接下来 $m_2$ 行，每行三个正整数 $u,v,w$，表示 $(u,v,w)\in E_2$。

输出格式

如果答案为无穷大，输出一行一个 $\texttt{-1}$。

否则输出一行一个非负整数表示答案。

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

-1

3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10

20

提示

• $2\le n\le 10^3$；
• $n-1\le m_1,m_2\le 10^5$；
• $1\le u,v\le n$，$1\le w\le 10^6$；
• $1\le s,t\le n$。