#include <iostream> #include <vector> #include <queue> #include <cassert> using namespace std; typedef long long ll; typedef pair<ll,int> P; int N,M,used[100010] = {}; vector<vector<P>> v(100010),tree(100010); ll dp[100010][2] = {},inf = 1e18; void dfs(int n,int m){ for(auto x:tree[n]){ if(x.second!=m){ dfs(x.second,n); dp[n][1] = min(dp[n][1],dp[x.second][1]+x.first); } } } int main(){ cin >> N >> M; assert(2<=N && N<=100000); assert(N-1<=M && M<=min(100000,N*(N-1)/2)); int a,b; ll c; for(int i=0;i<M;i++){ cin >> a >> b >> c; assert(1<=a && a<=N && 1<=b && b<=N && 1<=c && c<=1000000000); v[a].push_back(P(c,b)); v[b].push_back(P(c,a)); } for(int i=2;i<=N;i++){ dp[i][0] = inf; dp[i][1] = inf; } priority_queue<P,vector<P>,greater<P>> Q; Q.push(P(0,1)); while(!Q.empty()){ P p = Q.top(); Q.pop(); int n = p.second; used[n] = 1; if(dp[n][0]<p.first) continue; for(auto x:v[n]){ if(dp[n][0]==dp[x.second][0]+x.first){ tree[n].push_back(P(x.first,x.second)); tree[x.second].push_back(P(x.first,n)); } if(dp[x.second][0]>p.first+x.first){ dp[x.second][0] = p.first+x.first; Q.push(P(dp[x.second][0],x.second)); } if(used[x.second]!=1) dp[x.second][1] = min(min(dp[x.second][1],dp[n][1]+x.first),p.first); } } dfs(1,0); for(int i=1;i<=N;i++){ assert(dp[i][0]!=inf && dp[i][1]!=inf); //cerr << dp[i][0] << " " << dp[i][1] << endl; cout << dp[i][0]+dp[i][1] << endl; } }