#include #include #include #include using namespace std; typedef long long ll; typedef pair P; int N,M,used[100010] = {}; vector> v(100010); ll dp[100010][2] = {},inf = 1e18; int main(){ cin >> N >> M; assert(2<=N && N<=100000); assert(N-1<=M && M<=min(200000,N*(N-1)/2)); int a,b; ll c; for(int i=0;i> a >> b >> c; assert(1<=a && a<=N && 1<=b && b<=N && 1<=c && c<=1000000000); assert(a!=b); 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,greater

> Q,Q2; Q.push(P(0,1)); int cnt = 0; while(!Q.empty()){ P p = Q.top(); Q.pop(); int n = p.second; if(dp[n][0]p.first+x.first){ dp[x.second][0] = p.first+x.first; Q.push(P(dp[x.second][0],x.second)); } } } Q2.push(P(0,1)); while(!Q2.empty()){ P p = Q2.top(); Q2.pop(); int n = p.second; if(dp[n][1]min(dp[n][1]+x.first,dp[n][0])){ dp[x.second][1] = min(dp[n][1]+x.first,dp[n][0]); Q2.push(P(dp[x.second][1],x.second)); } } } for(int i=1;i<=N;i++){ assert(dp[i][0]!=inf && dp[i][1]!=inf); cout << dp[i][0]+dp[i][1] << endl; } }