#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef uint64_t ull; typedef pair P; typedef pair Pid; typedef pair Pdi; typedef pair Pl; typedef pair Pll; typedef pair> PP; typedef pair PPi; constexpr double PI = 3.1415926535897932; // acos(-1) constexpr double EPS = 1e-9; constexpr int INF = 1001001001; constexpr int mod = 1000000007; // constexpr int mod = 998244353; #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) #define chadd(x, y) x = (x + y) % mod struct Edge{ int to, cost; Edge() = default; Edge(int to, int cost) : to(to), cost(cost) {} }; using Info = tuple; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector> graph(n); vector> dp(n, vector(2, 1e+17)); for(int i = 0; i < m; ++i){ int a, b, c; cin >> a >> b >> c; --a, --b; graph[a].emplace_back(Edge(b, c)); graph[b].emplace_back(Edge(a, c)); } priority_queue, greater> que; dp[0][0] = 0, dp[0][1] = 0; que.push(Info(0, 0, 0)); que.push(Info(0, 1, 0)); while(!que.empty()){ Info p = que.top(); que.pop(); ll d; int state, from; tie(d, state, from) = p; if(d > dp[from][state]) continue; for(Edge e : graph[from]){ int to = e.to, cost = e.cost; if(dp[to][state] > d + cost){ dp[to][state] = d + cost; que.push(Info(dp[to][state], state, to)); } if(state == 0){ if(dp[to][1] > d){ dp[to][1] = d; que.push(Info(d, 1, to)); } } } } for(int i = 0; i < n; ++i) cout << dp[i][0] + dp[i][1] << "\n"; }