U141581 南天取经

由于吉林省突降冻雨暴雪，佛祖怜悯众生，传下三藏天气预报。$Seaway$为了天下苍生，自告奋勇，前去南天取经......（由于西边的印度疫情太严重，佛祖把极乐世界搬到了南方。）

就像当年唐三藏西天取经一样，$Seaway$南天取经也许下了宏大的愿望：不走回头路。佛祖深受感动，把所有道路变成了只能由北向南的单向通行，并且保证了这些道路不会让$Seaway$走回之前走过的地方。(......)临行之前，九天之上突降一卷天书。$Seaway$打开一看，原来是南天取经的地图。地图一共有$N$个位置。上面标示：$Seaway$的出发点长春在$1$号位置，而南方极乐世界在$N$号位置。地图上玄乎其玄地提示$Seaway$：一定要表现出你足够辛苦，这样才能打动上天。（注：经过的位置越多越辛苦）。但是$Seaway$的马儿只能支持走$K$千米。所以$Seaway$希望让自己在行进距离不超过$K$的情况下看起来更辛苦一些。请你告诉$Seaway$，他最多可以经过多少个位置。

无

无

对于$30\%$的数据，$1\le N,M\le 10,K>\sum w$。 对于$40\%$的数据，$1\le N,M\le 10,1\le K\le 10$。 对于$60\%$的数据，$1\le N,M\le 100,1\le K\le 100$。 对于全部数据，$1\le N,M\le 5\times 10^3,1\le K\le 10^9$。