题目描述

夕阳西下，匆匆忙忙间，SSJ一天的课程已经全部上完了，肚子咕咕开始叫了，坐上回家的公交车，可是SSJ今天好像有点迷，据说今中午吃饭时没去食堂，走着走着，外边景色好美啊，啊？我好像没走过这，完了，我好想迷路了。 公交车到了终点站，SSJ下车了，内心无比紧张，回不去了，一阵冷风吹过，瑟瑟发抖，emm...，那是一张地图？地图上有啥大家都明白，SSJ现在已经饿得无力思考了，请你帮他设计一条最快回家的路下，他要快点回家。

输入格式

第一行四个数n，m,s,t。(分别表示有地图上n个地点，m条道路，SSJ在s处，他家在t处) 第2-m+1三个正整数，f，u(某条路起点)，v(到达点)，w(路径距离)。 (f为1或0,1表示这条道路上有恶狗拦路，SSJ已无力与恶狗打斗了，所以他要避开这些道路，0表示此条道路无危险)。

输出格式

第一行一个数表示最短路径长度，若无法回家输出“My gold！！！”(无引号) 若可以回家，第二行表示SSJ行走的路线(从s到t，包括s和t)，每个点用空格隔开。

样例

5 7 1 5 
0 1 4 4 
1 1 3 2 
1 1 5 7 
1 2 5 10 
0 2 3 1 
1 3 5 2 
1 4 3 7

4 
1 3 5

提示

对于20%的数据$n \\le 10,m\\le100$。

对于60%的数据$n\\le100,m\\le10000$。

对于100%的数据$n\\le10000,m\\le200000,w\\le5000000$

来自机械20-2 任满意