#include using namespace std; typedef long long ll; #define F first #define S second #define pii pair #define eb emplace_back #define all(v) v.begin(), v.end() #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep3(i, l, n) for (int i = l; i < (n); ++i) #define sz(v) (int)v.size() #define inf (int)(1e9+7) #define abs(x) (x >= 0 ? x : -(x)) template inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; } template inline void chmax(T1 &a, T2 b) { if (a < b) a = b; } template inline T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); } int n, m; vector > > v(100005); const ll INF = 1e18; using P = pair; vector dijkstra(int n, vector > > edge, int s) { vector d(n, INF); priority_queue, greater

> que; //頂点、最短距離、小さい順に d[s] = 0; que.push(P(s, 0)); while (!que.empty()) { P p = que.top(); que.pop(); int cur = p.F; if (d[cur] < p.S) continue; rep(i, sz(edge[cur])) { int nxt = edge[cur][i].F; ll cost = edge[cur][i].S; if (d[nxt] > d[cur] + cost) { d[nxt] = d[cur] + cost; que.push(P(nxt, d[nxt])); } } } return d; } using p2 = pair >; auto dijkstra2(int n, vector > > edge, int s) { vector > d(n, vector(2)); rep(i, n) rep(j, 2) d[i][j] = INF; d[0][0] = 0; d[0][1] = 0; priority_queue, greater > que; //頂点、最短距離、小さい順に que.push(p2(s, P(0, 0))); // 頂点, コスト, 0,1 while (!que.empty()) { p2 p = que.top(); // 頂点, コスト que.pop(); if (p.S.S == 0) { for (auto nxt : v[p.F]) { if (chmin(d[nxt.F][0], p.S.F + nxt.S)) { // 0 -> 0 que.push(p2(nxt.F, P(d[nxt.F][0], 0))); } // 0 -> 1 if (chmin(d[nxt.F][1], p.S.F)) { // 0 -> 0 que.push(p2(nxt.F, P(d[nxt.F][1], 1))); } } } else { for (auto nxt : v[p.F]) { if (chmin(d[nxt.F][1], p.S.F + nxt.S)) { // 1 -> 1 que.push(p2(nxt.F, P(d[nxt.F][1], 1))); } } } } return d; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; rep(i, m) { int a, b, c; cin >> a >> b >> c; a--; b--; v[a].eb(pii(b, c)); v[b].eb(pii(a, c)); } auto di = dijkstra(n, v, 0); // rep(i, n) cout << di[i] << " "; cout << endl; auto di2 = dijkstra2(n, v, 0); // rep(i, n) cout << di2[i][1] << " "; cout << endl; rep(i, n) cout << di[i] + di2[i][1] << endl; }