#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

    using VI = vector<int>;
    using PI = pair <int, int>;
    using VP = vector<PI>;
    using VVP = vector<VP>;

const int inf = 0x3f3f3f3f;
int n;
    VVP G;
    VI d;
    void dijk(int x, VI& d) {

        priority_queue <VP, vector<PI>, greater<PI> >Q;

        d = VI(n + 1, inf);
        d[x] = 0;
        Q.emplace(0, x);

        while(!Q.empty()) {
            auto [dx, x] = Q.top();
            Q.pop();

            if (dx > d[x])
                continue;

            for (auto p : G[x]) {
                auto [y, w] = p;
                if (d[y] > d[x] + w) {
                    d[y] = d[x] + w;
                    Q.emplace(d[y], y);
                }
            }
        }

    }


int main()
{
    int m, i, j, x, y, w;
    cin >> n >> m;

    G = VVP(n + 1);

    for (i = 1; i <= m; ++i)
    {
        cin >> x >> y >> w;
        G[x].emplace_back(y, w);
    }

    dijk(1, d);

    for(j = 2; j <= n; ++j)
    if (d[j] == inf)
    cout << "0 ";
    else
        cout << d[j] << ' ';
    return 0;
}