9999026 - 魔法国度

小 G 来到了一个神奇的国度，在这个国家里人们可以随意的使用魔法。酷爱 旅行的小 G 决定在这个奇妙的国度旅行。 这个国家一共有 n 个城市，城市和城市之间以一条双向道路连接，通过每一 条双向道路都会花费一定的时间。整个国家一共有 m 条双向道路，任意两座城市 总可以直接或间接到达对方，且任意两座城市之间不会有超过一条的双向道路连 接双方。 为了方便旅行，小 G 学会了一种魔法：它能够在任意两座有着“魔法吸引” 关系的城市之间搭建一条不消耗时间通过的魔法通道，能够在一瞬间从一座城市 抵达另一座城市。两座城市有着“魔法吸引”关系当且仅当存在两条不经过重复 道路的路径连接着这两座城市。 小 G 可以使用无限次以上魔法，他现在在 1 号城市开始自己的旅程，因为小 G 是一个喜新厌旧的人，因此他不会遍历同一座城市两次。 现在他想知道，对于 i = 2 ∼ n，遍历 i 座城市的最少时间。(只有经过双向道 路时才会花费时间，魔法通道不花费时间

第一行一个整数 n, m，分别表示城市的个数与双向道路的数量。 接下来一共 m 行，第 i 行共三个整数 xi , yi , ti，表示第 i 个条双向道路连接城 市 xi 和 yi，通行时间为为 ti。

输出共 n − 1 行，第 i 行一个整数表示遍历 i + 1 座城市的最少时间，若不存 在遍历 i + 1 座城市的旅行方案请输出 ”INF”(不含引号)