最近小精灵在FJ的农场中泛滥了。他们经常会阻止奶牛们从谷仓（牛棚_1）走到别的牛棚（牛_i的目的地是牛棚_i）。每只小精灵只会骚扰一头牛，第i只小精灵会在牛_i从牛棚1到牛棚_i的最短路径上的最后一条路上骚扰牛_i。当然奶牛们不希望被小精灵们骚扰，所以准备找一条稍微不同的路径从牛棚_1走到牛棚_i。请你为每头牛_i找出一条在不被小精灵骚扰的前提下，从牛棚_1走到牛棚_i的最短路径。

农场上有N(3<=N<=100000)个编号为1...N的牛棚，M(2<=M<=200000)条连接牛棚的双向路，编号为1...M，道路i连接牛棚a_i(1<=a_i<=N)和b_i(1<=b_i<=N)，并且需要时间t_i(1<=t_i<=1000)通过。没有两条路连接同样的牛棚，即a_i!=b_i。道路保证能让所有牛在不考虑小精灵骚扰的情况下，到达他们的目的地，且在不考虑小精灵骚扰的前提下，牛_i从牛棚_1到牛棚_i的最短路径是唯一的。

第1行：两个空格分隔的整数N和M，表示牛棚的数量和道路的数量。

第2行到第M_1行：每行3个空格分隔的整数a_i, b_i和t_i，表示一条连接牛棚a_i和b_i的道路，通行时间为t_i。