#include "bits/stdc++.h" #define ALL(obj) (obj).begin(),(obj).end() #define RALL(obj) (obj).rbegin(),(obj).rend() #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define REPR(i, n) for(int i = (int)(n); i >= 0; i--) #define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++) using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int INF = MOD - 1; const ll LLINF = 4e18; // dijkstra法 struct edge { int to; ll cost; }; vector> G;//グラフ vector> d;//sからの距離(INFで初期化) void dijkstra(int s) { priority_queue, vector>, greater>> pq; d[s][0] = d[s][1] = 0; pq.push(tuple(0, 0, s)); pq.push(tuple(0, 1, s)); while (!pq.empty()) { tuple p = pq.top(); pq.pop(); int v = get<2>(p); if (d[v][get<1>(p)] < get<0>(p)) continue; for (edge e : G[v]) { if (d[e.to][0] > d[v][0] + e.cost) { d[e.to][0] = d[v][0] + e.cost; pq.push({d[e.to][0],0, e.to}); } if (d[e.to][1] > d[v][0]) { d[e.to][1] = min(d[v][0], d[v][1] + e.cost); pq.push({d[e.to][1],1, e.to}); } if (d[e.to][1] > d[v][1] + e.cost) { d[e.to][1] = min(d[v][0],d[v][1] + e.cost); pq.push({d[e.to][1],1, e.to}); } } } } int main() { int n, m; cin >> n >> m; G.resize(n); d.resize(n,vector(2,LLINF)); REP(i, m) { int a, b;ll c; cin >> a >> b >> c; a--; b--; G[a].push_back({b,c}); G[b].push_back({a,c}); } dijkstra(0); REP(i, n) { cout << d[i][0] + d[i][1] << endl; } getchar(); getchar(); }