typedef long long ll; #include using namespace std; template void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } typedef pair P; struct edge { ll to; ll cost; }; vector G[200010]; int main() { ll n,m; std::cin >> n>>m; ll d[200010]; ll inf = 100000000000000+10; Fill(d,inf); d[0] = 0; for (int i = 0; i < m; i++) { ll tmp_a,tmp_b,tmp_c; std::cin >> tmp_a>>tmp_b>>tmp_c; tmp_a--; tmp_b--; edge e1 = {tmp_b,tmp_c}; edge e2 = {tmp_a,tmp_c}; G[tmp_a].push_back(e1); G[tmp_b].push_back(e2); G[tmp_a].push_back({tmp_b+n,0}); G[tmp_b].push_back({tmp_b+n,0}); G[tmp_b+n].push_back({tmp_a+n,tmp_c}); G[tmp_a+n].push_back({tmp_b+n,tmp_c}); } priority_queue, greater

> que; que.push(P(0, 0)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first) continue; for (int i=0; i d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } for (int i = 0; i < n; i++) { if(i==0){ std::cout << 0 << std::endl; }else{ std::cout << d[i]+d[n+i]<< std::endl; } } }