U84985 Seaway找路

$Seaway$和他的女朋友即将在$JDFZ$开启他们的高中生活...但是不幸的是，万恶的分班考试没有让$Seaway$和女朋友分到一个班级(qwq)。浓烈的相思让他们决定在每天中午都去找对方......

$JDFZ$的校园是一个含有$N$个点、$M$条边的带权无向图。$Seaway$和女朋友一共要相会$P$天（$1 \le P \le 5000$），并且，每一天他们俩的位置都不确定（很奇妙吧）。每天中午，他们两个当然希望走最少的路就能和对方相见。但$Seaway$很快又遇到了难题：他不认路......（连$Seaway$都不认路，他的女朋友更不可能认路了），两个路痴怎么能顺利地相会呢？$Seaway$灵机一动，想到了一个办法：他要编写程序把每一天他们要走的路径输出出来，这样他和他的女朋友就可以顺顺利利地找到对方啦！但是$Seaway$不屑做这么简单的工作（其实是他不会），所以他把这个任务交给了你。

第一行包括两个整数：$N$，$M$。 接下来$M$行，每行三个整数$X,Y,Z$,表示$X,Y$之间有一条长为$Z$的边。 接下来是一个整数$P$，表示$Seaway$和女朋友一共要相会$P$天。 接下来的$P$行，每行两个整数$A,B$，表示这一天他们的位置为$A,B$。

输出有$P$行，每行包含若干个整数，表示$A,B$之间最短路的路径（输出包含$A,B$并按升序输出）。如果$A,B$之间不存在最短路，输出qwq。

提示： 不排除$Seaway$一开始就和女朋友在一起的情形。 数据范围： $1 \le N \le 100$,$1 \le M \le 10000$。