#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(M); 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)); } int DP[N]; REP(i, N) DP[i] = INT_MAX; auto c = [](pos l, pos r) { return l.second > r.second; }; priority_queue, decltype(c)> q(c); DP[0] = 0; q.push(*new pos(0, 0)); while(!q.empty()) { pos item = q.top(); q.pop(); int index = item.first; int cost = item.second; for (auto route: R[index]) { int ni = route.first; int newCost = cost + route.second; if (newCost < DP[ni]) { DP[ni] = newCost; q.push(*new pos(ni, newCost)); } } } // REP(i, N) cout << DP[i] << endl; // first: total cost, second: longest cost vector DP2(N); REP(i, N) DP2[i].first = INT_MAX; DP2[0].first = 0; DP2[0].second = 0; q.push(*new pos(0, 0)); while(!q.empty()) { pos item = q.top(); q.pop(); int index = item.first; int totalCost = DP2[index].first; int longest = DP2[index].second; for (auto route: R[index]) { int ni = route.first; int newCost = totalCost + route.second; int newLongest = max(longest, route.second); int currentFactCost = DP2[ni].first - DP2[ni].second; int factCost = newCost - newLongest; if (factCost < currentFactCost) { DP2[ni].first = newCost; DP2[ni].second = newLongest; q.push(*new pos(ni, factCost)); } } } REP(i, N) cout << DP[i] + DP2[i].first - DP2[i].second << endl; return 0; }