#include <fstream>
#include <vector>
#include <queue>
#define N 50001
#define INF 2147483647

using namespace std;

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

int n;
vector<pair<int, int>> a[N];
priority_queue<pair<int, int>> h;
long long d[N];

void citire() {
    int m, x, y, c;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> c;
        a[x].push_back(make_pair(y, c));
    }
}

void dijkstra(int x0) {
    int x, y;
    long long c;
    pair<int, int> p;
    for(int i = 1; i <= n; i++) {
        d[i] = INF;
    }
    d[x0] = 0;
    h.push(make_pair(-d[x0], x0));

    while(!h.empty()) {
        while (!h.empty() && d[h.top().second] < -h.top().first) {
            h.pop();
        }
        if (h.empty()) {
            return;
        }
        x = h.top().second;
        h.pop();
        for (int i = 0; i < a[x].size; i++) {
            y = a[x][i].first;
            c = a[x][i].second;
            if (d[x] + c < d[y]) {
                d[y] = d[x] + c;
                h.push(make_pair(-d[y], y));
            }
        }
    }
}

int main()
{
    citire();
    dijkstra(1);
    for(int i = 2; i <= n; i++)
    {
        if(d[i] == INF)
            fout << 0 << ' ';
        else
            fout << d[i] << ' ';
    }
    return 0;
}