U618868 小鸟公主の新冒险！

小鸟公主又一次踏上了旅途...

在一片有 $n$ 个地点可以探索的森林中，小鸟公主发现了 $m$ 条可以去的路，每条路连接了 $u$ 和 $v$ 两个地区，因为森林太茂密了小鸟公主决定沿着路飞，飞这段路需要花费小鸟公主 $t$ 天。 **请注意道路是可以双向行走的** 。小鸟公主想知道对于地图上的任意两个地点最快多久可以到达，可是小鸟公主还要继续她的冒险呢！于是她向你寻求帮助，如果帮帮她，小鸟公主会蹭蹭你给你唱歌的哦~~

一行两个数 $n,m$ 表示有 $n$ 个地点以及 $m$ 条路。 接下来 $m$ 行，每行三个数 $u,v,t$ 分别表示这条路连接的两个地点以及飞这条路要花费的天数。 一行一个数 $q$ 表示小鸟公主的 $q$ 次询问。 每次询问给出两个地点 $u,v$，表示小鸟公主要询问的两个地方。

对于 $q$ 次询问，请输出 $q$ 行答案，每行答案为小鸟公主询问的两个地方要到达花费的最少天数，特别的，如果到达不了请告诉小鸟公主 ``` 404 NOT FOUND ```

数据范围与约定: **所有数据均为整数** $2\leq n\leq500$ $1\leq m,q\leq10^5$ $1\leq u,v\leq n$ $1\leq t\leq10^9$ *完整的故事在这里：* 经历了上一次的冒险之后，小鸟公主常常会想起自己以前的小小经历，而且她也有点想念她的朋友们了。这一天，小飞鼠又来探望小鸟公主，小鸟公主忍不住又掉了好多小珍珠。“你怎么了呀？”小飞鼠问。“我想念我们的冒险了！”小鸟公主有点失落的坐在她的小王座上。“既然这样，”小飞鼠揉了揉小鸟公主的脸，“我们就再度出发吧，我的小公主！”于是他们再次踏上了旅途。 就像所有故事的开始一样，他们走在以前一起走过的路上，分享以前和此刻的快乐和悲伤。他们飞过了一片森林和一片湖泊，停在小猫咪以前的窝前。小鸟公主看着落灰的躺椅有点难过的说“上一次我们就在这里遇到了小猫咪呢，可是现在她不再和我们同行了...”想着想着，小鸟公主忍不住落下来小珍珠。“没事啦，”小飞鼠安慰小鸟公主说，“现在她在牧羊人的小木屋里过的也不错哩！等我们去看望她的时候说不定还能听听她这些日子的有趣经历呢！”小鸟公主听了之后拍拍翅膀，想到懒懒的小猫咪躺在暖炉旁边的样子觉得心情好了一些，于是两个好朋友继续出发了。 他们经过了一片小山，还穿过了一片麦田来到海边。在海边他们一起看了金灿灿的日出。看着阳光照在麦子上的光，小鸟公主又有点难过了，她想起了那条被小猫咪抓起来的小鱼也曾经被太阳照得这样闪闪发光。小飞鼠看出了小鸟公主的小心思，对她说：“我的小公主呀，要和我一起在麦子上飞一飞吗，以前我们来的时候麦子还没成熟呢，现在我有幸可以和你共享这一片麦田的清香吗？”小鸟公主知道小飞鼠不想她总是难过，于是就与她一起飞去了麦田，在麦田里他们遇到了麦田的主人稻田鸭，稻田鸭还和他们分享了小麦和露水，休整了一晚后他们再次出发了。 飞着飞着，小鸟公主和小飞鼠被太过茂密的森林整的有些迷糊了，就在两个小伙伴不知道怎么办的时候，小羊从小路的一旁欢快的跑到了他们身边。“咩咩！我的朋友们好久不见呀！你们来这里做客了嘛！”小鸟公主和小飞鼠看到老朋友的出现非常高兴，于是跟着小羊一起到了牧羊人的小木屋。小木屋外小猫咪正躺在草垛上晒太阳。“你好呀，喜欢你们来ω”小猫咪欢快的跳下了草垛。几个小伙伴终于又聚到了一起。他们开始说着那么多的太阳和月亮落下又升起的时候他们经历的日子，一直说到星星也出来。“明天也可以继续说啦，日子还长呢ω”小猫咪伸了个懒腰提醒小伙伴们。于是小鸟公主和小飞鼠去树洞里休息了，小羊和小猫咪则呆在小木屋里睡了一晚。 又过了几日，像所有故事的最后一样，一群小伙伴又要分别了。小鸟公主和小飞鼠挥挥翅膀和好朋友们道别，他们带着满满的故事回家了。不久后小鸟公主就回到了她的王国，再次唱起旅途里欢快的歌。可是再新鲜的故事也有说完的那一天，慢慢的，小鸟公主说完了她的故事，可是小鸟公主已经拥有了再次踏上旅途的勇气，她知道总会有人和她一起踏上旅途，我如此相信着... > 感谢你耐心读完了 $Whizney$ 写的故事，作为奖励 $Whizney$ 可以给你一个小小的提示，要注意地图上可能会有两个地方之间有不同的路连接哦 $^w^$