#include <fstream> 
#include <vector>
#include <queue>
#define INT_MAX 2000000000

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

int n, m;
int d[50005];
std::vector<std::pair<int, int>> L[50005];
std::priority_queue<std::pair<int, int>> q;

void dijkstra(int S) {
    for (int i = 1; i <= n; i++) {
        d[i] = INT_MAX;
    }
    d[S] = 0;
    q.push(std::make_pair(0, S));
    while (!q.empty()) {

        auto[c, x] = q.top();
        q.pop();

        if (c != d[x]) {
            continue;
        }

        for (auto w : L[x]) {
            if (d[w.first] > w.second - c) {
                d[w.first] = w.second - c;
                q.push(std::make_pair(-d[w.first], w.first));
            }
        }
    }
}

int main() {
    int x, y, c;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        L[x].push_back(std::make_pair(y, c));
    }

    dijkstra(1);
    for (int i = 2; i <= n; i++) {
        fout << (d[i] == INT_MAX ? 0 : d[i]) << " ";
    }
    fout << "\n";
    fout.close();
}