#include <bits/stdc++.h>

using namespace std;

#define INF 1000000000
#define MAXN 50000

priority_queue <pair <int, int> > q;
vector <pair <int, int> >g[MAXN+1];
int dist[MAXN+1];
int n;

void dijkstra(int start) {
    int son, node, cost, dist_son, i;
    for(i=1; i<=n; i++)
        dist[i]=INF;
    dist[start]=0;
    q.push({start, 0});
    while(!q.empty()) {
        node=q.top().first;
        cost=-q.top().second;
        q.pop();
        if(cost<=dist[node])
            for(i=0; i<g[node].size(); i++) {
                son=g[node][i].first;
                dist_son=-g[node][i].second;
                if(dist[son]>dist_son+cost) {
                    dist[son]=dist_son+cost;
                    q.push({son, -dist[son]});
                }
            }
    }

}

int main()
{
    int m, a, b, cost, i;
    FILE *fi, *fo;
    fi = fopen("dijkstra.in", "r");
    fo = fopen("dijkstra.out", "w");
    fscanf(fi, "%d%d", &n, &m);
    for(i=0; i<m; i++) {
        fscanf(fi, "%d%d%d", &a, &b, &cost);
        g[a].push_back({b, -cost});
    }
    dijkstra(1);
    for(i=2; i<=n; i++) {
        if(dist[i]==INF)
            dist[i]=0;
        fprintf(fo, "%d ", dist[i]);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}