U219895 瓜皮旅行团(终极)

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

不过，有些景点与景点之间有通过的路，但有些没有。 路一共被分为三种： ①畅通之路，可直接通过。 ②高速之路，需要交 $x$ 元才可以通过。 ③优惠之路，可以免费赠送 $x$ 元。 对于每一条路，只可以单向通过，即： $1,3$ 相连，则 $1\to3$ 合法，但 $3\to1$ 不合法。 现在有 $n$ 个瓜皮景点， $m$ 条路，并从第 $s$ 个景点进入，第 $t$ 个景点出来，请你帮帮小杨求出最少的花费元数吧！(不一定每个景点都要去，也不是每个景点最多去 $1$ 遍) 由于小杨被要求马上写出方案，又不想浪费太多内存（虽然电脑升级了，但电脑被游戏[偷偷告诉你，游戏名曰Minecraft，最占内存的游戏]占领了，也就剩下 $1$MB），所以请你在 $150ms$ 的时间和 $1$MB (这可是全部财产！)的内存下完成。

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

第一行，一个整数，表示从第 $s$ 个景点到第 $t$ 个景点所需花费最少的元数。(无法到达，答案超过 $100000000$ ，或者存在一个环路可以无限刷钱，均输出" $Nonsense!$ ") 第二行，输出满足要求的最短路径，形式如下： “$a_n\gets a_{n-1}\gets\dots\gets a_5\gets a_4\gets a_3\gets a_2\gets a_1$”，共过了 $n$ 个景点。 (如果有多条，输出字典序最大的)

$1 ≤ n ≤ 50000$ $1 ≤ m ≤ 1000$ $1 ≤ a,b ≤ n$ $1 ≤ c ≤ 3$ $1 ≤ k ≤ 100$ $1 ≤ s,t ≤ n$ ### 本题为[yzc20100218](https://www.luogu.com.cn/user/510713)原创，未经允许，禁止改编、套用