#include <bits/stdc++.h>

using namespace std;

struct way {
    int y, c;

    bool operator < (const way& way2) const {
        return c > way2.c;
    }
};

int M, N, S;
vector<vector<way>> G;
vector<int> D;
vector<int> C;
vector<bool> V;

/*void bfs(int node) {
    queue<int> Q;
    Q.push(node);
    D[node] = 0;
    while(!Q.empty()) {
        node = Q.front();
        Q.pop();
        if(V[node])
            continue;
        V[node] = true;
        for(auto neigh : G[node]) {
            if(D[neigh] == -1) {
                D[neigh] = D[node] + 1;
                Q.push(neigh);
            }
        }
    }
}*/

/*bool bellman(int node)
{
    queue<int> Q;
    Q.push(node);
    D[node] = 0;
    while(!Q.empty())
    {
        node = Q.front();
        Q.pop();
        if(C[node] > N)
            return false;

        for(pair<int, int> neigh : G[node])
        {
            int cost = neigh.second;
            if(D[neigh.first] > cost + D[node])
            {
                D[neigh.first] = cost + D[node];
                Q.push(neigh.first);
                C[neigh.first]++;
            }
        }
    }

    return true;
}*/

void dijkstra(int node) {
    priority_queue<int> Q;
    Q.push(node);
    D[node] = 0;
    while(!Q.empty()) {
        node = Q.top();
        Q.pop();
        if(V[node])
            continue;
        V[node] = true;

        for(auto neigh : G[node]) {
            if(D[neigh.y] > D[node] + neigh.c) {
                D[neigh.y] = D[node] + neigh.c;
                Q.push(neigh.y);
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    cin >> N >> M;

    G.resize(N + 1);
    D.resize(N + 1);
    V.resize(N + 1);
    fill(D.begin(), D.end(), INT_MAX);
    fill(V.begin(), V.end(), false);

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        way drum;
        drum.y = y;
        drum.c = c;
        G[x].push_back(drum);
    }

    dijkstra(1);

    for(int i = 1; i <= N; i++) {
        cout << D[i] << " ";
    }

    return 0;
}