{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"话说这个王铁牛是怎么来的呢?\u003cbr\u003e\n因为这货太喜欢吹牛了,所以呢\u003cbr\u003e\n大家都说:\"铁牛啊,铁牛.就知道吹牛\"\u003cbr\u003e\n这不,有一天铁牛又开始吹了。\u003cbr\u003e\n铁牛说自己每天下学,只沿着符合条\n件的(A,B)道路回家,(A,B)道路是肯定存在一条从B点出发的回家的路径,比所有从A点出发的回家的路径距离都要短。\u003cbr\u003e\nCqw说:\"王铁牛,你又开始吹牛的了!\"\u003cbr\u003e\n铁牛不回答,只是自言自语说:\"我只要知道每个点离家的最近距离就行了。\"\u003cbr\u003e\nCqw又说:\"你一定是复制了别人的最短路模板吧?\"\u003cbr\u003e\n王铁牛睁大眼睛说,\"你怎么这样凭空污人清白……\"\u003cbr\u003e\n\"什么清白?我前天亲眼见你偷了别人的代码,连注释都不改,被人家吊着打\"\u003cbr\u003e\n王铁牛便涨红了脸,额上的青筋条条绽出,争辩道,“贴代码不能算偷……窃代码!……码农的事,能算偷么?”\u003cbr\u003e\n接连便是难懂的话,什么“最短路径”,什么“DP”之类,引得众人都哄笑起来:店内外充满了快活的空气。\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cbr\u003e多组数据输入\u003cbr\u003e\n每组数据的第一行是两个整数n,m(1\u0026lt;\u003dn\u0026lt;\u003d1000)\u003cspan\u003e\n它们分别表示点的数目和边的数目。\u003cbr\u003e点的编号范围是 1 至 n。\n边的数量为m。\u003cnr\u003e\n之后m行每行是3个整数a,b,c代表a点与b点之间有一条长度为c的双向道路(1\u003c/span\u003e\u0026lt;\u003dc\u0026lt;\u003d10^\u003cspan\u003e6)\u003cbr\u003e\n当n\u003d0时结束输入\u003cbr\u003e\n由于王铁牛被怀疑贴代码\u003cbr\u003e所以本题的难度就提升了,要求输出王铁牛一共有多少种符合条件的回家的路径\u003cbr\u003e\n忘了说,王铁牛起点的编号为1,家的编号也就是终点的编号为2"}},{"title":"Output","value":{"format":"HTML","content":"\u003cbr\u003e每组数据输出一行表示王铁牛回家的路径的条数,保证答案在(2^\u003cspan\u003e31)-1的范围内。"}},{"title":"Sample Input","value":{"format":"HTML","content":"5 6\u003cbr\u003e\n1 3 2\u003cbr\u003e\n1 4 2\u003cbr\u003e\n3 4 3\u003cbr\u003e\n1 5 12\u003cbr\u003e\n4 2 34\u003cbr\u003e\n5 2 24\u003cbr\u003e\n7 8\u003cbr\u003e\n1 3 1\u003cbr\u003e\n1 4 1\u003cbr\u003e\n3 7 1\u003cbr\u003e\n7 4 1\u003cbr\u003e\n7 5 1\u003cbr\u003e\n6 7 1\u003cbr\u003e\n5 2 1\u003cbr\u003e\n6 2 1\u003cbr\u003e\n0"}},{"title":"Sample Output","value":{"format":"HTML","content":"2\u003cbr\u003e\n4\u003cbr\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e改了题面,向原作者致歉\u003cbr\u003e\n可以从A点走到B点的要求是\u003cbr\u003e\nA-B有一条路径\u003cbr\u003e\n并且\nB到家的最小距离要小于A到家的最短距离\n"}}]}