#include "bits/stdc++.h" #define Rep(i,n) for(int i=0;i> a(n,vector(m,0)); using namespace std; typedef long long ll; typedef pair P; template inline bool chmax(T& a, T b) {if(a inline bool chmin(T& a, T b) {if(a>b){a=b;return 1;}return 0;} struct edge{ int to,cost; }; int n,m; vector> g; vector> d(2); int main(){ cin >> n >> m; d[0].resize(n); d[1].resize(n); g.resize(n); vector a(m); vector b(m); vector c(m); REP(i,m){ cin >> a[i] >> b[i] >> c[i]; a[i]--;b[i]--; edge e1; e1.to = b[i]; e1.cost = c[i]; g[a[i]].push_back(e1); edge e2; e2.to = a[i]; e2.cost = c[i]; g[b[i]].push_back(e2); } priority_queue,greater

> q; fill(all(d[0]),1e16); fill(all(d[1]),1e16); d[0][0]=d[1][0]=0; q.push(P(0,0)); while(!q.empty()){ P p = q.top();q.pop(); int v = p.second; //if(d[0][v]d[0][v]+e.cost){ d[0][e.to] = d[0][v]+e.cost; q.push(P(d[0][e.to],e.to)); } chmin(d[1][e.to],min(d[1][v]+e.cost,d[0][v])); } } REP(i,n){ put(d[1][i]+d[0][i]); } return 0; }