A国的边境上修建了n座兵营（编号为1~n），某些兵营之间修建了用于传达消息的双向道路，不同的道路由于长度和平整度不同，也就可能需要不同的天数才能走完。

为方便指挥作战，A国将指挥所修建在了1号兵营。当指挥部下达作战指令后，指挥部就派出若干个传令兵，按照预先修好的道路，将指令传达给相邻的兵营。当一座兵营接到指令后，会按同样的方式向其他兵营传达指令，直到所有的兵营都收到作战指令。

请编程计算出，从指挥部发出作战指令到所有兵营都收到作战命令，最短需要多少天。

第一行有两个整数n和m，表示有n个兵营和m条道路。1 ≤ n ≤ 100，1 ≤ m ≤ 500。

第2至m+1行，每行三个整数x, y, k，表示第x个和第y个兵营之间存在一条需要k天才能走完的双向道路。

输出所有兵营接到指令的最短天数，如果由于道路的缺失，导致无论如何都不能做到所有兵营都能接到指令，请输出-1。

图论