#include "bits/stdc++.h" using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define array2(type, x, y) array, x> #define vector2(type) vector > #define out(...) //printf(__VA_ARGS__) typedef pair pos; int pos::*x = &pos::first; int pos::*y = &pos::second; int dxy[] = {0, 1, 0, -1, 0}; /*================================*/ int N, M, a, b, c; int A[20], B[20]; signed main() { #if DEBUG std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); #endif cin >> N >> M; vector< vector > R(N); REP(i, M) { cin >> a >> b >> c; a--; b--; R[a].push_back(*new pos(b, c)); R[b].push_back(*new pos(a, c)); } // without skip, with skip vector DP(N); REP(i, N) DP[i].first = DP[i].second = LONG_MAX; DP[0].first = DP[0].second = 0; auto c = [](pos l, pos r) { return l.second > r.second; }; priority_queue, decltype(c)> q(c); q.push(*new pos(0, 0)); while(!q.empty()) { pos item = q.top(); q.pop(); int index = item.first; for (auto route: R[index]) { int ni = route.first; { // without skip int newCost = DP[index].first + route.second; if (newCost < DP[ni].first) { DP[ni].first = newCost; q.push(*new pos(ni, newCost)); } } { // with current skip int newCost = DP[index].first; if (newCost < DP[ni].second) { DP[ni].second = newCost; q.push(*new pos(ni, newCost)); } } { // with prev skip int newCost = DP[index].second + route.second; if (newCost < DP[ni].second) { DP[ni].second = newCost; q.push(*new pos(ni, newCost)); } } } } REP(i, N) cout << DP[i].first + DP[i].second << endl; return 0; }