#include<cstdio>
#include<queue>
#include<vector>
#define MAXN 50100
#define INF 0x3f3f3f3f

using namespace std;

queue<int> q;
vector<int> L[MAXN], C[MAXN];
int d[MAXN];
int n, m;

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

    if (scanf("%d%d", &n, &m)) ;

    for(int i=2; i<=n; ++i)
        d[i]=INF;

    int x, y, c;
    while(m--) {
        if (scanf("%d%d%d",&x,&y,&c));
        L[x].push_back(y);
        C[x].push_back(c);
    }

    q.push(1);
    while (!q.empty()) {
        x = q.front();
        for (int i=0; i<L[x].size(); ++i)
            if (d[L[x][i]] > d[x] + C[x][i]) {
                //actualizam drumul minim
                d[L[x][i]] = d[x] + C[x][i];
                q.push(L[x][i]);
            }
        q.pop();
    }

    for(int i = 2; i <= n; i++)
        printf("%d ", d[i] == INF ? 0 : d[i]);

    return 0;
}