有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”马尔代夫？我也想去！没有人不向往一场说走就走的旅行！“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！
“哇，感觉我们像凡尔纳的《环游地球八十天》，好激动！可是老妈你也太 out 了，学计算机的最短路线你用手算？”暴汗……，“小子你别牛，你知道怎么算？”
“呃，好像是叫什么迪科斯彻的人会算。”
哈哈，关键时刻还要老妈上场了！
根据题目描述可知，这是一个求单源最短路径的问题。
给定有向带权图 G =（V，Ｅ），其中每条边的权是非负实数。此外，给定 V 中的一个顶点，称为源点。现在要计算从源到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。
第一行输入T组样例；
第二行输入图的点数n和边数m；
接下来m行输入u v w（分别为起点和终点以及边权）；
最后一行输入小明的位置pos。
输出小明到每个点的最短距离，中间用空格分隔 ，行尾没有空格（对于到不了的地方输出impossible）。
1
5 11
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
5
8 24 23 30 0