U219641 瓜皮旅行团(中级)

为了参加“瓜皮自有黄金屋”比赛，瓜皮们都十分拼命，导致大家都非常的劳累与辛苦。小杨(原名“ziruiya”)作为一名有素质的赛事主办方，十分理解各位瓜皮的辛苦，于是决定带大家到全世界的瓜皮景点散散心。

不过，有些景点与景点之间有通过的路，但有些没有。 路一共被分为两种： ①畅通之路，可直接通过。 ②高速之路，需要交 $x$ 元才可以通过。 对于每一条路，都可双向通过，即： $1,3$ 相连，则 $1 \to 3$ 和 $3\to 1$ 都合法，且交费数相等。 （如果为畅通之路，则均不收费） 现在有 $n$ 个瓜皮景点， $m$ 条路，并从第 $s$ 个景点进入，第 $t$ 个景点出来，请你帮帮小杨求出最少的花费元数吧！(不一定每个景点都要去，也不是每个景点最多去 $1$ 遍) 由于小杨被要求马上写出方案，又不想浪费太多内存（虽然电脑升级了，但电脑也只剩下 $5$MB内存），所以请你在 $50ms$ 的时间和 $3$MB 的内存下完成。

共 $m+2$ 行，其中: 第 $1$ 行，两个整数 $n,m$ ，分别表示景点个数和路个数。 第 $2 \sim m+1$ 行，每行先输入三个整数 $a,b,c$ ，表示第 $a$ 个景点与第 $b$ 个景点之间有一条属于 $c$ 类型的路： 如果 $c = 1$ ，则此路为畅通之路。 如果 $c = 2$ ，则此路为高速之路，后面再输入一个数 $k$ ，表示收费 $k$ 元。 第 $m+2$ 行，两个整数 $s,t$ ，表示从第 $s$ 个景点进入，第 $t$ 个景点出来。(保证 $s$ 不等于 $t$ )

仅一行，一个整数，表示从第 $s$ 个景点到第 $t$ 个景点所需花费最少的元数。(无法到达，输出"$Nonsense!$")

$1 ≤ n ≤ 10000$ $1 ≤ m ≤ 500000$ $1 ≤ a,b ≤ n$ $1 ≤ c ≤ 2$ $1 ≤ k ≤ 10000$ $1 ≤ s,t ≤ n$ (保证没有死循环，且结果为 $long$ $long$ 范围内的数) ### 本题为[yzc20100218](https://www.luogu.com.cn/user/510713)原创，未经允许，禁止改编、套用