PIPI的家乡有n个村落，n个村落之间由m条双向道路连接，每通过一条道路需要缴纳一定的手续费，保证这n个村落联通。
现在PIPI在1号村落开了一家公司，他要往2号/3号/.../n号村落运输物资。 
为了减少运输成本，PIPI和各村村长签订了协议。当他从1号村落到达某号村落并开始给村内搬运物资时，村长会帮他免除路径上手续费最贵的那条道路的费用，但是相反，PIPI也要多支出路径上手续费最便宜的那条道路的费用。协议内容必须执行。
请你帮PIPI计算，从1号村落到其他村落并开始给村内搬运物资时所需的最少费用是多少？

第一行两个正整数n和m，2<=n<=10^5,m<=2*10^5。
接下来m行，每行三个正整数u,v,w，表示u号村落与v号村落之间有一条需要缴纳w元费用的道路。其中：u<=n,v<=n,w<=10^9。
数据可能会有重边与自环。

输出n-1行，第i行的数字表示PIPI从1号村落到i+1号村落并开始给村内搬运物资时所需的最少费用。