Subway (subway, 2s, 512M)

Byteland 有 $n$ 个城市和 $n!$ 辆私家车。由于交通不便，市民们怨声载道。今天，市长宣布 Byteland 多了 $k$ 条高速地铁。每条高速地铁由若干段组成，每段连接两个城市里的对应地铁的地铁站，且只由每条高速地铁就可以从每个城市到达其他所有城市。

每个城市都有所有高速地铁对应的 $k$ 个地铁站。根据设计不同，在每个城市进和出每个地铁站需要一定的时间，且进站需要付对应高速地铁的一张票。一旦进站了，在出站之前你可以任意使用该高速地铁对应的段进行穿梭。由于 Byteland 科技先进，你并不需要等待地铁，所以乘坐每段需要的时间是已知的。由于每条高速地铁由不同的公司承建，要从地铁 $x$ 到地铁 $y$，你需要出站（走出地铁 $x$ 的地铁站）再进站（走进同一城市中地铁 $y$ 的地铁站）。

你现在处于城市 $1$。使用一些手段，你获得了 $k$ 种高速地铁的票各一张，你希望使用高速地铁到达城市 $n$。注意你开始并不在任何地铁站中，且你不能在地铁站内结束旅途（即你需要在城市 $n$ 出站后结束）。你想知道所需的最短时间。

输入格式

第一行两个正整数 $n,k$，表示城市数和高速地铁数。

对于每个高速地铁 $t\in [1,k]$，首先输入两行。第一行 $n$ 个非负整数 $a_{t,i}$ 表示城市 $i$ 进地铁 $t$ 对应站所需时间，第二行 $n$ 个非负整数 $b_{t,i}$ 表示城市 $i$ 出地铁 $t$ 对应站所需时间。接下来一行一个正整数 $m_t$，表示该地铁的段数。对于每一段输入一行三个非负整数 $u,v,w$，表示该段连接的两个地铁站所在城市 $u,v$（$u\ne v$）和乘坐该段所需时间 $w$。

保证仅使用每个高速地铁都能从任意一个城市到达其他所有城市，且每个高速地铁在每两个城市之间最多只有一个段。

输出格式

输出一个非负整数，表示从城市 $1$ 到城市 $n$ 所需的最短时间。

样例输入1

4 2
1 2 1 4
4 3 2 1
4
2 1 2
2 3 39
4 2 48
3 4 1
1 1 2 2
1 0 0 1
3
1 4 29
2 3 3
4 3 7

样例输出1

18

一种最优策略是 $1$ 号线从城市 $1$ 坐到城市 $2$，用时 $1$（城市 $1$ 进站）$+2$（乘坐城市 $1$ 到城市 $2$ 的那段地铁）$+3$（城市 $2$ 出站），再用 $2$ 号线从城市 $2$ 坐到城市 $4$，用时 $1$（城市 $2$ 进站）$+3$（乘坐城市 $2$ 到城市 $3$ 的那段地铁）$+7$（乘坐城市 $3$ 到城市 $4$ 的那段地铁）$+1$（城市 $4$ 出站），总用时 $18$。

样例输入2

2 2
0 0
0 0
1
2 1 1
0 0
0 0
1
1 2 2

样例输出2

1

不一定要用完所有的票。

样例输入3、样例输出3

见选手文件夹下 ex_subway3.in 和 ex_subway3.ans。

样例输入4、样例输出4

见选手文件夹下 ex_subway4.in 和 ex_subway4.ans。记得爆int。

数据范围

对于所有数据，$2\le n\le 500$，$n-1\le m_t\le 1000$，$1\le k\le 8$，$0\le a_{t,i},b_{t,i},w\le 10^9$。

对于 20% 的数据，$n\le 5$，$k\le 2$。

对于 30% 的数据，$n\le 100$，$k\le 3$。

对于 50% 的数据，$n\le 100$，$k\le 5$。

对于 70% 的数据，$k\le 6$。

对于另外 10% 的数据，$k=1$。