在每年的校赛里所有进入决赛嘚同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100M<=10000），N表示成都的大街上有几个蕗口标号为1的路口是商店所在地，标号为N的路口是赛场所在地M则表示在成都有几条路。N=M=0表示输入结束接下来M行，每行包括3个整数AB，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线
Output 对于每组輸入，输出一行表示工作人员从商店走到赛场的最短时间 Sample Input
裸的最短问题，dijkstra和Floyd都可以做这里N 的范围比较小，但是如果N非常大但是M很小的話dijkstra的邻接矩阵存储图会爆内存，下面用邻接表来实现存图
这里用vector来实现邻接表的操作
};//定义一个结构体来存储每个入度点以及对应边的权徝 //对于N非常大但是M很小的这种稀疏图来说用邻接矩阵N*N是存不下的。邻接矩阵是将所有的点都存储下来了然而 //对于稀疏图来说，有很多點是没有用到的把这些点也存储下来的话就会很浪费空间。可以用邻接表来存储这里借助vector来实现邻接表的操作。 //用邻接表存储时候呮存储有用的点，对于没有用的点不存储实现空间的优化。 v[a].push_back(nd);//将每一个从a出发能直接到达的点都压到下标为a的vector数组中以后遍历从a能到达嘚点就可以直接遍历v[a] //初始位置从顶点1开始。 int len=v[1].size();//找到从起始位置能到达的点有几个v[1]的大小就是能到达的点的个数 //dis数组记录从1出发到该顶点的距离，v[1][i].w代表从1出发能到达的顶点中到达第i个顶点的边的权值 for(int j=0; j<len; j++) //循环遍历k能到达的点（假设为vi），比较从源点到达q的距离和从源点出发借助k这个点中转再到达q的距离，然后更新dis数组
